24. Lexicographically Largest String After K Deletions
✅ GFG solution to the Lexicographically Largest String After K Deletions problem: remove exactly k characters to get the largest possible string using greedy approach. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given a string s consisting of lowercase English letters and an integer k, your task is to remove exactly k characters from the string. The resulting string must be the largest possible in lexicographical order, while maintaining the relative order of the remaining characters.
📘 Examples
Example 1
Input: s = "ritz", k = 2
Output: "tz"
Explanation: By removing two characters in all possible ways, we get:
"ri", "rt", "rz", "it", "iz", and "tz". Among these, "tz" is lexicographically largest.Example 2
Input: s = "zebra", k = 3
Output: "zr"
Explanation: Removing "e", "b", and "a" results in "zr", which is lexicographically largest.🔒 Constraints
$1 \le \text{s.size()} \le 10^5$
$0 \le k < \text{s.size()}$
String consists of lowercase English letters only
✅ My Approach
The optimal approach uses a Greedy Algorithm with Monotonic Stack concept to achieve the lexicographically largest result:
Greedy String Manipulation
Core Strategy:
Remove smaller characters when a larger character appears, as long as we have deletions remaining.
This ensures we keep the largest possible characters in their relative positions.
Algorithm Steps:
Iterate through each character in the string.
While the result string is not empty, we have deletions left, and the last character in result is smaller than current character:
Remove the last character from result (this counts as one deletion).
Add the current character to the result.
After processing all characters, resize the result to final length (n - k).
Key Insight:
By removing smaller characters when larger ones appear, we maximize the lexicographical value of the remaining string.
The greedy choice at each step leads to the globally optimal solution.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once when added, once when potentially removed), resulting in linear time complexity.
Expected Auxiliary Space Complexity: O(n), as we use a result string that can grow up to the size of the input string during processing.
🧑💻 Code (C++)
class Solution {
public:
string maxSubseq(string &s, int k) {
int n = s.length(), toRemove = k;
string res;
for (char c : s) {
while (!res.empty() && toRemove && res.back() < c) {
res.pop_back();
toRemove--;
}
res += c;
}
res.resize(n - k);
return res;
}
};🧑💻 Code (Java)
class Solution {
public static String maxSubseq(String s, int k) {
int n = s.length(), toRemove = k;
StringBuilder res = new StringBuilder();
for (int i = 0; i < n; i++) {
while (toRemove > 0 && res.length() > 0 && res.charAt(res.length() - 1) < s.charAt(i)) {
res.deleteCharAt(res.length() - 1);
toRemove--;
}
res.append(s.charAt(i));
}
res.setLength(n - k);
return res.toString();
}
}🐍 Code (Python)
class Solution:
def maxSubseq(self, s, k):
n, toRemove, res = len(s), k, []
for c in s:
while res and toRemove and res[-1] < c:
res.pop()
toRemove -= 1
res.append(c)
return ''.join(res[:n - k])🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated