Lexicographically Largest String After Deleting K Characters

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Get lexicographically largest string by deleting exactly k characters. Greedy with monotonic stack.

Algorithm

1Use stack. For each char: while stack not empty and top < current and k > 0: pop, k--. Push current.
2If k > 0: pop from end. Collect stack as result.

Common Pitfalls

•Similar to LC 402 but maximizing. Pop smaller characters greedily. Reverse comparison from minimum-removal.

Lexicographically Largest String After Deleting K Characters.java

Java

// Approach: Greedy with monotonic stack. Remove characters that are smaller than the next character while k > 0.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public String maxSubseq(String s, int k) {
        Stack<Character> st = new Stack<>();
        int n = s.length();
        int count = k;

        for (char i : s.toCharArray()) {
            if (st.isEmpty())
                st.push(i);
            else {
                while (!st.isEmpty() && count > 0 && st.peek() < i) {
                    st.pop();
                    count--;
                }
                st.push(i);
            }
        }

        while (st.size() > n - k)
            st.pop();

        StringBuilder ans = new StringBuilder();

        while (!st.isEmpty())
            ans.append(st.pop());

        return ans.reverse().toString();
    }
}

Was this solution helpful?