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