Lexicographically Smallest String after Removing k Characters

Problem Statement

Given a string s, we must:

1. Modify the value of k based on the length of the string.

2. Remove exactly k characters from the string.

3. 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:

1. Remove larger characters from the stack while removals remain.

2. 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.

Similar problems include:

• Remove K Digits

• Smallest Subsequence

• Lexicographically Smallest String

• Monotonic Stack Optimization

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.