Lexicographically smallest after removing k

Time: O(n)

Space: O(n)

Intuition

To minimize lexicographic order after deletions, remove earlier larger characters whenever a smaller incoming character can replace them. A stack naturally supports this greedy behavior. The problem-specific rule first transforms k depending on whether the string length is a power of two, then exactly that many removals are applied.

Algorithm

1Compute effective removals t: if n is power of 2, t = k/2; otherwise t = 2*k.
2Traverse characters and maintain a stack of kept characters.
3While stack top is greater than current character and removals used < t, pop stack (delete).
4Push current character onto stack.
5After traversal, if removals are still left, pop from the end until exactly t deletions are used.
6Build final string from stack; if empty, return -1.

Example Walkthrough

Input: s = "cbad", k = 1 (n=4, power of 2 => t=0)

1.Effective deletions t = 0, so no removals are allowed.
2.Stack simply stores all characters in order: c, b, a, d.
3.Result is original string "cbad".

Output: cbad

Common Pitfalls

•Use transformed deletion count t, not raw k.
•Greedy pops must stop once deletion budget is exhausted.
•If all characters are deleted, return -1 instead of empty string.

Lexicographically smallest after removing k.java

Java


import java.util.*;

// Approach: Greedy stack-based deletion budget. Adjust k based on whether length is power of 2,
// then maintain a monotonic stack and remove larger previous characters when a smaller one arrives,
// ensuring lexicographically smallest result after exactly k removals.
// Time: O(n) Space: O(n)

class Solution {

    public String lexicographicallySmallest(String s, int k) {
        Stack<Character> st = new Stack<>();
        int n = s.length();
        if (ispower(n)) {
            k = k / 2;
        } else {
            k = k * 2;
        }
        int t = k;
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (st.isEmpty()) {
                st.push(s.charAt(i));
                k--;
            } else {
                if (k != 0 && (int) st.peek() <= (int) s.charAt(i)) {
                    st.push(s.charAt(i));
                    k--;
                } else {
                    while (!st.isEmpty()) {
                        if ((int) st.peek() > (int) s.charAt(i)) {
                            if (cnt != t) {
                                st.pop();
                                cnt++;
                            } else {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    st.push(s.charAt(i));
                }
            }
        }
        StringBuilder s1 = new StringBuilder();
        while (!st.isEmpty()) {
            if (cnt != t) {
                cnt++;
                st.pop();
            } else {
                s1.append(st.pop());
            }
        }
        String m = s1.reverse().toString();
        return m.equals("") ? "-1" : m;
    }

    public Boolean ispower(int n) {
        if (n <= 0) {
            return false;
        }

        while (n % 2 == 0) {
            n = n / 2;
        }

        return n == 1;
    }
}

Was this solution helpful?