Remove K Digits (Monotonic Stack)

🎯

Remove K Digits (Monotonic Stack)

mediumSTACKAmazonGoogleFacebook

Imagine you have a large number displayed on a screen, but you want to make it as small as possible by removing exactly k digits. How do you do it efficiently?

💡 This problem is about removing digits to get the smallest possible number. Beginners often struggle because the naive approach tries all combinations, which is too slow. Understanding how to use a stack to maintain a monotonic sequence is key to solving it efficiently.

📋

Problem Statement

Given a non-negative integer num represented as a string and an integer k, remove k digits from the number so that the new number is the smallest possible. Return the new number as a string without leading zeros. If the result is empty, return "0".

1 ≤ num.length ≤ 10^5num consists of only digits '0' to '9'0 ≤ k ≤ num.length

💡

Example

Input"num = \"1432219\", k = 3"

Output"1219"

Remove digits '4', '3', and '2' to get the smallest number '1219'.

Input"num = \"10200\", k = 1"

Output"200"

Remove the leading '1' to get '0200', which is '200' after removing leading zeros.

Input"num = \"10\", k = 2"

Output"0"

Removing both digits leaves an empty string, so return '0'.

• k equals the length of num → output '0'
• num consists of all identical digits → remove k digits from the end
• num has leading zeros after removal → remove leading zeros in output
• k is zero → output is the original number

⚠️

Common Mistakes

Not removing leading zeros in the final result

Output has unwanted leading zeros, failing correctness

✅ Strip leading zeros before returning the result

Not removing remaining digits if k > 0 after iteration

Result is larger than possible because not enough digits removed

✅ Remove last k digits from stack after main loop

Using recursion or brute force for large inputs

Code times out or crashes due to exponential complexity

✅ Use the greedy monotonic stack approach for efficiency

Comparing strings incorrectly or not handling empty string

Incorrect minimum number chosen or runtime errors

✅ Use lexicographical comparison and handle empty string as '0'

🧠

Brute Force (Generate All Combinations)

💡 This approach exists to understand the problem deeply by trying all possible ways to remove k digits. It is impractical for large inputs but helps grasp the problem's combinatorial nature.

Intuition

Try every combination of removing k digits and pick the smallest resulting number. This brute force method guarantees correctness but is very inefficient.

Algorithm

1. Generate all combinations of indices to remove of size k.
2. For each combination, build the number by skipping those indices.
3. Compare all generated numbers and keep track of the smallest.
4. Return the smallest number after removing leading zeros or '0' if empty.

💡 The challenge is generating all combinations and comparing results, which is conceptually simple but computationally expensive.

</>

Code

from itertools import combinations

def removeKdigits(num: str, k: int) -> str:
    n = len(num)
    if k == n:
        return "0"
    min_num = None
    indices = range(n)
    for remove_indices in combinations(indices, k):
        remove_set = set(remove_indices)
        candidate = ''.join(num[i] for i in range(n) if i not in remove_set).lstrip('0')
        if candidate == '':
            candidate = '0'
        if min_num is None or candidate < min_num:
            min_num = candidate
    return min_num

# Driver code
if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # Expected: "1219"

Line Notes

from itertools import combinationsImport combinations to generate all removal sets

if k == n:If we remove all digits, result is '0'

for remove_indices in combinations(indices, k):Try every combination of k indices to remove

candidate = ''.join(num[i] for i in range(n) if i not in remove_set).lstrip('0')Build candidate number skipping removed digits and strip leading zeros

import java.util.*;

public class RemoveKDigitsBrute {
    public static String removeKdigits(String num, int k) {
        int n = num.length();
        if (k == n) return "0";
        String minNum = null;
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < n; i++) indices.add(i);
        List<List<Integer>> combos = combinations(indices, k);
        for (List<Integer> removeIndices : combos) {
            Set<Integer> removeSet = new HashSet<>(removeIndices);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (!removeSet.contains(i)) sb.append(num.charAt(i));
            }
            String candidate = sb.toString().replaceFirst("^0+", "");
            if (candidate.isEmpty()) candidate = "0";
            if (minNum == null || candidate.compareTo(minNum) < 0) minNum = candidate;
        }
        return minNum;
    }

    private static List<List<Integer>> combinations(List<Integer> arr, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(arr, k, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(List<Integer> arr, int k, int start, List<Integer> temp, List<List<Integer>> result) {
        if (temp.size() == k) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < arr.size(); i++) {
            temp.add(arr.get(i));
            backtrack(arr, k, i + 1, temp, result);
            temp.remove(temp.size() - 1);
        }
    }

    // Driver
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3)); // Expected: "1219"
    }
}

Line Notes

if (k == n) return "0";If all digits removed, return '0'

for (List<Integer> removeIndices : combos)Try every combination of indices to remove

String candidate = sb.toString().replaceFirst("^0+", "");Remove leading zeros from candidate

if (minNum == null || candidate.compareTo(minNum) < 0)Keep track of lex smallest candidate

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void backtrack(const vector<int>& arr, int k, int start, vector<int>& temp, vector<vector<int>>& result) {
    if ((int)temp.size() == k) {
        result.push_back(temp);
        return;
    }
    for (int i = start; i < (int)arr.size(); i++) {
        temp.push_back(arr[i]);
        backtrack(arr, k, i + 1, temp, result);
        temp.pop_back();
    }
}

vector<vector<int>> combinations(const vector<int>& arr, int k) {
    vector<vector<int>> result;
    vector<int> temp;
    backtrack(arr, k, 0, temp, result);
    return result;
}

string removeKdigits(string num, int k) {
    int n = (int)num.size();
    if (k == n) return "0";
    vector<int> indices(n);
    for (int i = 0; i < n; i++) indices[i] = i;
    vector<vector<int>> combos = combinations(indices, k);
    string minNum = "";
    for (auto& removeIndices : combos) {
        set<int> removeSet(removeIndices.begin(), removeIndices.end());
        string candidate = "";
        for (int i = 0; i < n; i++) {
            if (removeSet.find(i) == removeSet.end()) candidate += num[i];
        }
        candidate.erase(0, candidate.find_first_not_of('0'));
        if (candidate.empty()) candidate = "0";
        if (minNum.empty() || candidate < minNum) minNum = candidate;
    }
    return minNum;
}

int main() {
    cout << removeKdigits("1432219", 3) << endl; // Expected: 1219
    return 0;
}

Line Notes

if (k == n) return "0";Return '0' if all digits removed

vector<vector<int>> combos = combinations(indices, k);Generate all combinations of indices to remove

candidate.erase(0, candidate.find_first_not_of('0'));Remove leading zeros from candidate

if (minNum.empty() || candidate < minNum) minNum = candidate;Track lex smallest candidate

function removeKdigits(num, k) {
    const n = num.length;
    if (k === n) return "0";
    const indices = [...Array(n).keys()];
    function combinations(arr, k) {
        const result = [];
        function backtrack(start, temp) {
            if (temp.length === k) {
                result.push([...temp]);
                return;
            }
            for (let i = start; i < arr.length; i++) {
                temp.push(arr[i]);
                backtrack(i + 1, temp);
                temp.pop();
            }
        }
        backtrack(0, []);
        return result;
    }
    const combos = combinations(indices, k);
    let minNum = null;
    for (const removeIndices of combos) {
        const removeSet = new Set(removeIndices);
        let candidate = '';
        for (let i = 0; i < n; i++) {
            if (!removeSet.has(i)) candidate += num[i];
        }
        candidate = candidate.replace(/^0+/, '');
        if (candidate === '') candidate = '0';
        if (minNum === null || candidate < minNum) minNum = candidate;
    }
    return minNum;
}

// Driver
console.log(removeKdigits("1432219", 3)); // Expected: "1219"

Line Notes

if (k === n) return "0";Return '0' if all digits removed

function combinations(arr, k)Generate all combinations of indices to remove

candidate = candidate.replace(/^0+/, '');Remove leading zeros from candidate

if (minNum === null || candidate < minNum) minNum = candidate;Track lex smallest candidate

⏱

Complexity

TimeO(n choose k * n)

SpaceO(n choose k * n)

We generate all combinations of k indices to remove (n choose k), and for each, build a candidate string of length up to n.

💡 For n=10 and k=3, this means thousands of combinations and millions of operations, which is impractical for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Greedy + Stack (Monotonic Increasing Stack)

💡 This approach uses a stack to greedily remove digits that are larger than the next digit, ensuring the smallest possible number. It is efficient and the standard solution.

Intuition

We want to remove digits that make the number larger when a smaller digit follows. Using a stack, we pop larger digits before pushing smaller ones, removing up to k digits.

Algorithm

1. Initialize an empty stack.
2. Iterate over each digit in num:
3. While k > 0 and stack top is greater than current digit, pop from stack and decrement k.
4. Push current digit onto stack.
5. If k > 0 after iteration, remove last k digits from stack.
6. Build the number from stack and remove leading zeros.
7. Return '0' if result is empty.

💡 The key is the while loop that ensures the stack remains monotonic increasing, removing larger digits before smaller ones.

</>

Code

def removeKdigits(num: str, k: int) -> str:
    stack = []
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # If k still remains, remove from the end
    stack = stack[:-k] if k else stack
    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

# Driver code
if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # Expected: "1219"

Line Notes

stack = []Initialize stack to build the final number

while k > 0 and stack and stack[-1] > digit:Remove larger digits before smaller ones to minimize number

stack = stack[:-k] if k else stackIf removals remain, remove from the end (largest digits at the end)

result = ''.join(stack).lstrip('0')Build final number and remove leading zeros

import java.util.*;

public class RemoveKDigits {
    public static String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char digit : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peekLast() > digit) {
                stack.pollLast();
                k--;
            }
            stack.offerLast(digit);
        }
        while (k > 0) {
            stack.pollLast();
            k--;
        }
        StringBuilder sb = new StringBuilder();
        boolean leadingZero = true;
        for (char c : stack) {
            if (leadingZero && c == '0') continue;
            leadingZero = false;
            sb.append(c);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }

    // Driver
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3)); // Expected: "1219"
    }
}

Line Notes

Deque<Character> stack = new ArrayDeque<>();Use deque as stack to store digits

while (k > 0 && !stack.isEmpty() && stack.peekLast() > digit)Pop larger digits before smaller ones to minimize number

while (k > 0)Remove remaining digits from the end if k still positive

if (leadingZero && c == '0') continue;Skip leading zeros when building result

#include <iostream>
#include <string>
#include <deque>

using namespace std;

string removeKdigits(string num, int k) {
    deque<char> stack;
    for (char digit : num) {
        while (k > 0 && !stack.empty() && stack.back() > digit) {
            stack.pop_back();
            k--;
        }
        stack.push_back(digit);
    }
    while (k > 0 && !stack.empty()) {
        stack.pop_back();
        k--;
    }
    string result;
    bool leadingZero = true;
    for (char c : stack) {
        if (leadingZero && c == '0') continue;
        leadingZero = false;
        result.push_back(c);
    }
    return result.empty() ? "0" : result;
}

int main() {
    cout << removeKdigits("1432219", 3) << endl; // Expected: 1219
    return 0;
}

Line Notes

deque<char> stack;Use deque as stack to hold digits

while (k > 0 && !stack.empty() && stack.back() > digit)Pop larger digits before smaller ones to minimize number

while (k > 0 && !stack.empty())Remove remaining digits from the end if k still positive

if (leadingZero && c == '0') continue;Skip leading zeros when building final string

function removeKdigits(num, k) {
    const stack = [];
    for (const digit of num) {
        while (k > 0 && stack.length && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    while (k > 0) {
        stack.pop();
        k--;
    }
    let result = stack.join('').replace(/^0+/, '');
    return result === '' ? '0' : result;
}

// Driver
console.log(removeKdigits("1432219", 3)); // Expected: "1219"

Line Notes

const stack = [];Initialize stack to build the number

while (k > 0 && stack.length && stack[stack.length - 1] > digit)Pop larger digits before smaller ones to minimize number

while (k > 0)Remove remaining digits from the end if k still positive

result = stack.join('').replace(/^0+/, '')Build final number and remove leading zeros

⏱

Complexity

TimeO(n)

SpaceO(n)

Each digit is pushed and popped at most once, so linear time. Stack uses linear space.

💡 For n=100000, this means about 200000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the optimal and accepted approach for this problem in interviews.

🧠

Greedy + Stack with StringBuilder Optimization

💡 This approach is a minor optimization of the previous stack method, using a mutable string builder to reduce overhead in some languages.

Intuition

Same greedy monotonic stack idea, but build the result incrementally with a string builder or similar structure for efficiency.

Algorithm

1. Initialize an empty string builder to simulate a stack.
2. Iterate over each digit in num:
3. While k > 0 and last character in builder is greater than current digit, remove last character and decrement k.
4. Append current digit to builder.
5. If k > 0 after iteration, remove last k characters from builder.
6. Remove leading zeros from builder.
7. Return '0' if builder is empty.

💡 This approach is logically identical to the previous but uses string manipulation for performance.

</>

Code

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    if k > 0:
        builder = builder[:-k]
    result = ''.join(builder).lstrip('0')
    return result if result else '0'

# Driver
if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # Expected: "1219"

Line Notes

builder = []Use list as mutable string builder

while k > 0 and builder and builder[-1] > digit:Remove larger digits before smaller ones

if k > 0: builder = builder[:-k]Remove remaining digits from end if needed

result = ''.join(builder).lstrip('0')Build final string and remove leading zeros

public class RemoveKDigitsOptimized {
    public static String removeKdigits(String num, int k) {
        StringBuilder builder = new StringBuilder();
        for (char digit : num.toCharArray()) {
            while (k > 0 && builder.length() > 0 && builder.charAt(builder.length() - 1) > digit) {
                builder.deleteCharAt(builder.length() - 1);
                k--;
            }
            builder.append(digit);
        }
        while (k > 0 && builder.length() > 0) {
            builder.deleteCharAt(builder.length() - 1);
            k--;
        }
        while (builder.length() > 0 && builder.charAt(0) == '0') {
            builder.deleteCharAt(0);
        }
        return builder.length() == 0 ? "0" : builder.toString();
    }

    // Driver
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3)); // Expected: "1219"
    }
}

Line Notes

StringBuilder builder = new StringBuilder();Use StringBuilder for efficient string manipulation

while (k > 0 && builder.length() > 0 && builder.charAt(builder.length() - 1) > digit)Remove larger digits before smaller ones

while (k > 0 && builder.length() > 0)Remove remaining digits from end if needed

while (builder.length() > 0 && builder.charAt(0) == '0')Remove leading zeros

#include <iostream>
#include <string>

using namespace std;

string removeKdigits(string num, int k) {
    string builder;
    for (char digit : num) {
        while (k > 0 && !builder.empty() && builder.back() > digit) {
            builder.pop_back();
            k--;
        }
        builder.push_back(digit);
    }
    while (k > 0 && !builder.empty()) {
        builder.pop_back();
        k--;
    }
    size_t pos = builder.find_first_not_of('0');
    if (pos == string::npos) return "0";
    return builder.substr(pos);
}

int main() {
    cout << removeKdigits("1432219", 3) << endl; // Expected: 1219
    return 0;
}

Line Notes

string builder;Use string as mutable builder simulating stack

while (k > 0 && !builder.empty() && builder.back() > digit)Remove larger digits before smaller ones

while (k > 0 && !builder.empty())Remove remaining digits from end if needed

size_t pos = builder.find_first_not_of('0');Find first non-zero to remove leading zeros

function removeKdigits(num, k) {
    let builder = '';
    for (const digit of num) {
        while (k > 0 && builder.length > 0 && builder[builder.length - 1] > digit) {
            builder = builder.slice(0, -1);
            k--;
        }
        builder += digit;
    }
    while (k > 0) {
        builder = builder.slice(0, -1);
        k--;
    }
    builder = builder.replace(/^0+/, '');
    return builder === '' ? '0' : builder;
}

// Driver
console.log(removeKdigits("1432219", 3)); // Expected: "1219"

Line Notes

let builder = '';Use string as mutable builder

while (k > 0 && builder.length > 0 && builder[builder.length - 1] > digit)Remove larger digits before smaller ones

while (k > 0)Remove remaining digits from end if needed

builder = builder.replace(/^0+/, '');Remove leading zeros

⏱

Complexity

TimeO(n)

SpaceO(n)

Same linear time and space complexity as previous approach, with minor performance improvements.

💡 This approach is just a practical optimization of the monotonic stack method.

Interview Verdict: Accepted

This is a slight optimization but logically equivalent to the optimal approach.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the greedy monotonic stack approach (Approach 2 or 3) for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n choose k * n)	O(n choose k * n)	Yes (deep recursion in combinations)	Yes	Mention only - never code
2. Greedy + Stack	O(n)	O(n)	No	Yes	Code this approach
3. Greedy + Stack with StringBuilder Optimization	O(n)	O(n)	No	Yes	Code if language-specific optimization needed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the greedy intuition and monotonic stack approach.Step 4: Write clean, optimal code using the stack method.Step 5: Test your code with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to greedy, coding skills, and handling of edge cases.

Common Follow-ups

• What if k is zero? → Return original number after removing leading zeros.
• How to handle very large input efficiently? → Use the monotonic stack approach with O(n) time.

💡 These follow-ups check if you handle trivial cases and scale your solution.

🔍

Pattern Recognition

When to Use

1) Asked to remove k elements to minimize/maximize a sequence; 2) Need smallest/largest number after removals; 3) Problem hints at removing larger elements before smaller; 4) Monotonic stack or greedy approach fits.

Signature Phrases

"remove k digits to get smallest number""monotonic increasing stack"

NOT This Pattern When

Problems that require subsequence or substring without removals or that use DP for counting distinct sequences.

Similar Problems

Create Maximum Number - similar removal and ordering logicRemove Duplicate Letters - uses monotonic stack to maintain order

Practice

1. Consider the following Python function that computes the largest rectangle area in a histogram using a monotonic stack approach. Given the input heights = [2, 1, 5], what is the value of the variable right after computing the right boundaries (just before calculating max_area)?

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [1, 3, 3]

D. [3, 3, 3]

Solution

1. Step 1: Trace right boundary computation for i=2 (height=5)

   Stack is empty, so right[2] = n = 3, stack = [2]

2. Step 2: Trace i=1 (height=1)

   Pop indices with height >= 1: pop 2 (height=5), stack empty, right[1] = 3, stack = [1]

3. Step 3: Trace i=0 (height=2)

   Stack top is 1 (height=1) < 2, so right[0] = 1, stack = [1,0]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Right boundaries correctly reflect next smaller bar indices [OK]

Hint: Right boundaries found by scanning from right with stack [OK]

Common Mistakes:

• Confusing indices or off-by-one in right boundary
• Not clearing stack before right boundary pass

2. You are given a binary matrix and need to find the largest rectangle containing only 1s. Which approach guarantees an optimal solution with O(rows * cols) time complexity?

easy

A. Use dynamic programming to store the largest rectangle ending at each cell without histogram transformation.

B. Use brute force to check all possible rectangles in the matrix.

C. Transform each row into a histogram of heights and apply a monotonic stack to find the largest rectangle in each histogram.

D. Apply a greedy approach by expanding rectangles from each cell until a zero is encountered.

Solution

1. Step 1: Understand the problem transformation

   The problem can be transformed row-wise into histograms where each element represents the height of consecutive 1s above it.

2. Step 2: Recognize the monotonic stack pattern

   For each histogram, the largest rectangle can be found efficiently using a monotonic stack that tracks indices of increasing heights.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Histogram + monotonic stack approach is standard for maximal rectangle [OK]

Hint: Transform rows to histograms and use monotonic stack [OK]

Common Mistakes:

• Trying brute force leads to O(n^4) time
• Greedy expansion fails on complex shapes
• DP without histogram misses efficient stack usage

3. Consider the following MinStack implementation using a single stack with encoded minimums. After executing the sequence push(3), push(5), push(2), pop(), what is the value returned by getMin()?

easy

A. None

B. 3

C. 5

D. 2

Solution

1. Step 1: Trace push(3)

   Stack empty, push 0, minVal=3.

2. Step 2: Trace push(5)

   diff=5-3=2>0, push 2, minVal=3.

3. Step 3: Trace push(2)

   diff=2-3=-1<0, push -1, minVal=2.

4. Step 4: Trace pop()

   pop -1 (negative), minVal=2 - (-1)=3.

5. Step 5: getMin()

   minVal=3.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   After popping 2, min is restored to 3 [OK]

Hint: Negative diff updates minVal on push and pop [OK]

Common Mistakes:

• Forgetting to update minVal on pop
• Returning old minVal after pop
• Confusing top value with minVal

4. What is the time complexity of the optimal stack-based decoding algorithm for a string of length n with maximum repeat count max_k?

medium

A. O(n * max_k)

B. O(n)

C. O(n^2)

D. O(n log max_k)

Solution

1. Step 1: Identify loops and string expansions

   The algorithm iterates over n characters, but each decoded substring can be repeated up to max_k times, causing repeated concatenations.

2. Step 2: Analyze string multiplication cost

   Multiplying substrings by count k can cause up to O(n * max_k) time in worst case, as repeated expansions dominate.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Repeated expansions cause linear times max_k complexity [OK]

Hint: String repeats multiply runtime by max_k [OK]

Common Mistakes:

• Assuming O(n) ignoring repeat expansions
• Confusing max_k with log factor

5. The following code attempts to find the longest valid parentheses substring using a stack-based approach. Identify the line containing the subtle bug that causes incorrect results for inputs starting with valid parentheses at index 0.

def longestValidParentheses(s: str) -> int:
    stack = []
    max_len = 0
    stack.append(-1)  # Initialize stack with -1
    for i, ch in enumerate(s):
        if ch == '(': 
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

medium

A. Line 4: stack initialized with -1

B. Line 9: popping from stack without checking if empty

C. Line 3: stack initialized as empty list

D. Line 12: resetting stack with current index when empty

Solution

1. Step 1: Analyze stack pop operation

   Line 9 pops from stack without checking if stack is empty, which can cause runtime error or incorrect behavior if stack is empty.

2. Step 2: Understand initialization and reset logic

   Stack initialized with -1 (line 4) is correct to handle valid substrings starting at index 0; resetting stack with current index (line 12) is also correct.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pop without empty check leads to subtle bugs on edge cases [OK]

Hint: Popping stack without empty check causes subtle bugs [OK]

Common Mistakes:

• Forgetting to initialize stack with -1
• Not checking stack emptiness before pop
• Incorrect reset of stack after imbalance