Lexicographically Smallest String After Removing K Characters Using a Monotonic Stack

Introduction

In many string manipulation problems, we are asked to remove a certain number of characters while preserving the relative order of the remaining characters. The goal is often to produce the smallest possible string in lexicographical (dictionary) order.

This problem adds an interesting twist: before removing characters, we must first modify the value of k based on the length of the string.

Let's understand the problem, derive an optimal solution, and implement it efficiently in Java.

Problem Statement

Given:

A string s consisting of lowercase English letters.
An integer k.

Before removing characters, correct the value of k as follows:

If the length of the string is a power of 2, reduce k by half.
Otherwise, multiply k by 2.

After correction, remove exactly k characters so that the resulting string is lexicographically smallest.

Return:

The smallest possible string.
-1 if it is impossible to remove the required number of characters or the resulting string becomes empty.

Example 1

Input

s = "fooland"
k = 2

Length = 7

7 is not a power of 2.

Corrected k:

k = 2 × 2 = 4

Remove 4 characters optimally:

fooland
 ↓↓↓↓
and

Output

"and"

Example 2

Input

s = "code"
k = 4

Length = 4

4 is a power of 2.

Corrected k:

k = 4 / 2 = 2

After removing 2 characters:

code → cd

Output

"cd"

Understanding Lexicographical Order

Lexicographical order is the same as dictionary order.

Examples:

abc < acb
cat < dog
and < fool

To obtain the smallest string, smaller characters should appear as early as possible.

Key Observation

Suppose we have:

cbad

and need to remove one character.

Keeping c at the beginning is not optimal because b is smaller.

If we remove c:

bad

which is lexicographically smaller.

This suggests:

Whenever a larger character appears before a smaller character, we should remove the larger one if removals are still available.

This is exactly where a Monotonic Stack helps.

Monotonic Stack Approach

We maintain characters in increasing order.

For every new character:

Compare it with the stack top.
If the top character is greater than the current character and removals remain:
- Remove the top character.
- Continue until no more beneficial removals exist.
Push the current character.

This guarantees the smallest possible prefix at every step.

Step-by-Step Example

Input

s = "fooland"
k = 2

Length = 7

Corrected:

k = 4

Processing

Read 'f'

Stack: f

Read 'o'

Stack: fo

Read 'o'

Stack: foo

Read 'l'

Remove larger characters:

foo
  ^
remove o

fo
 ^
remove o

Stack:

fl

Remaining removals:

k = 2

Read 'a'

remove l
remove f

Stack:

Remaining removals:

k = 0

Read 'n'

an

Read 'd'

and

Final answer:

and

Checking Whether Length Is a Power of 2

A number is a power of 2 if:

(n & (n - 1)) == 0

Example:

4  = 100
3  = 011

100 & 011 = 000

Therefore:

4 is a power of 2

Java Solution

class Solution {

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

    public String lexicographicallySmallest(String s, int k) {

        int n = s.length();

        // Correct k
        if (isPowerOfTwo(n)) {
            k /= 2;
        } else {
            k *= 2;
        }

        // Impossible case
        if (k >= n) {
            return "-1";
        }

        StringBuilder stack = new StringBuilder();

        for (char ch : s.toCharArray()) {

            while (k > 0 &&
                   stack.length() > 0 &&
                   stack.charAt(stack.length() - 1) > ch) {

                stack.deleteCharAt(stack.length() - 1);
                k--;
            }

            stack.append(ch);
        }

        // Remove remaining characters from end
        while (k > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }

        String ans = stack.toString();

        return ans.length() == 0 ? "-1" : ans;
    }
}

Dry Run

Input

s = "code"
k = 4

Length:

4 → power of 2

Corrected:

k = 2

Processing

c → c
o → co
d → remove o
     cd
e → cde

Still need one removal:

remove e

Result:

cd

Output

"cd"

Complexity Analysis

Time Complexity

O(n)

Each character is pushed and popped at most once.

Space Complexity

O(n)

For the stack used to build the answer.

Why This Approach Works

The algorithm follows a greedy strategy:

Remove larger characters whenever a smaller character appears later.
Create the smallest possible prefix at every step.
Use all removals efficiently.

Since each character is processed once, the solution is optimal for strings up to:

n = 100000

which satisfies the problem constraints.

Conclusion

The "Lexicographically Smallest String After Removing K Characters" problem combines two important concepts:

Power-of-two bit manipulation.
Monotonic stack-based greedy optimization.

By first correcting k and then using a monotonic stack to remove larger preceding characters, we can generate the lexicographically smallest possible string in linear time.

This approach runs in O(n) time and O(n) space, making it suitable for large inputs and coding interview scenarios.