Lexicographically Smallest String after Removing k Characters

Problem Statement

Given a string s, we must:

Modify the value of k based on the length of the string.
Remove exactly k characters from the string.
Return the lexicographically smallest possible resulting string.

If it is not possible to perform the operation or the resulting string becomes empty, return:

-1

Special Adjustment of k

Before removing characters, adjust k according to the length of the string.

Case 1: Length Is a Power of 2

If the length of s is a power of 2:

k = k / 2

Case 2: Length Is Not a Power of 2

Otherwise:

k = k * 2

Understanding the Goal

We need to form the smallest possible string in dictionary (lexicographical) order.

Example

Between:

bac

and

abc

the smaller string is:

abc

because 'a' < 'b'.

To minimize the final string:

Smaller characters should appear as early as possible.
Larger characters should be removed whenever beneficial.

Key Idea

This is a classic Monotonic Stack problem.

The strategy is:

Remove larger characters before smaller characters whenever possible.

This greedy approach ensures the resulting string is lexicographically minimal.

Greedy Strategy

We process the string from left to right while maintaining a stack.

Rule

While processing each character:

The stack is not empty.
We still have removals available (k > 0).
The current character is smaller than the stack top.

Remove the stack top.

Then push the current character.

Why?

If a smaller character appears later, removing a larger character before it makes the overall string smaller lexicographically.

Power of Two Check

Before processing the string, determine whether its length is a power of two.

A number is a power of two if:

n & (n - 1) == 0

Examples:

n	Power of 2
1	Yes
2	Yes
4	Yes
8	Yes
7	No
10	No

Algorithm

Step 1: Adjust k

Compute:

n = s.length()

If n is a power of two:

k = k / 2

Otherwise:

k = k * 2

Step 2: Validate

If:

k > n

return:

-1

because removing more characters than available is impossible.

Step 3: Build the Smallest String

Traverse the string.

For each character:

Remove larger characters from the stack while removals remain.
Push the current character.

Step 4: Remove Remaining Characters

If removals are still left after traversal:

Remove characters from the end

because the stack is already in the best possible form.

Step 5: Return Result

If the final string is empty:

-1

Otherwise, return the constructed string.

Example Walkthrough

Input

s = "fooland"
k = 2

Step 1: Adjust k

Length:

n = 7

Since 7 is not a power of two:

k = 2 × 2 = 4

Step 2: Process Characters

The greedy stack removes larger characters whenever a smaller character appears.

After removing four characters optimally:

and

Output

"and"

Why the Stack Works

The stack maintains characters in an increasing lexicographical order whenever possible.

Whenever a smaller character arrives:

larger previous characters become less desirable

and are removed if removals remain.

This guarantees that every local decision contributes toward the globally smallest string.

Java Solution

import java.util.*;

class Solution {

    private boolean isPowerOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }

    public String lexicographicallySmallest(String s, int k) {
        int n = s.length();

        // Step 1: adjust k
        if (isPowerOfTwo(n)) {
            k = k / 2;
        } else {
            k = k * 2;
        }

        if (k > n) return "-1";

        Stack<Character> st = new Stack<>();

        // Step 2: greedy stack processing
        for (char ch : s.toCharArray()) {
            while (!st.isEmpty() && k > 0 && st.peek() > ch) {
                st.pop();
                k--;
            }
            st.push(ch);
        }

        // Step 3: remove remaining k from end
        while (k > 0 && !st.isEmpty()) {
            st.pop();
            k--;
        }

        if (st.isEmpty()) return "-1";

        StringBuilder sb = new StringBuilder();
        for (char ch : st) {
            sb.append(ch);
        }

        return sb.toString();
    }
}

Complexity Analysis

Time Complexity

Each character:

Is pushed onto the stack at most once.
Is popped from the stack at most once.

Therefore:

O(n)

Space Complexity

The stack can store up to n characters.

O(n)

Pattern Recognition

This problem combines multiple interview patterns:

Bit Manipulation

Used to determine whether the string length is a power of two.

Greedy Optimization

Always remove larger characters before smaller ones whenever possible.

Monotonic Stack

Maintains the optimal sequence of characters while processing the string.

Key Takeaway

The most important observation is that lexicographical order is determined by earlier characters. Therefore, whenever a smaller character can replace a larger character appearing before it, removing the larger character is always beneficial. A monotonic stack efficiently implements this greedy strategy, producing the smallest possible string after exactly k removals.

Summary

To obtain the lexicographically smallest string, first adjust k based on whether the string length is a power of two. Then use a monotonic stack to greedily remove larger characters whenever a smaller character appears. Any remaining removals are applied from the end of the stack. This approach combines bit manipulation, greedy decision-making, and monotonic stack techniques to achieve an efficient O(n) solution.