1.
Introduction to Problem Statement
1.1.
Sample Examples
1.2.
What is lexicographic order
2.
Approach
3.
Implementation
3.1.
Implementation in C++
3.2.
Implementation in Java
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Lexicographically largest String after removal of K characters

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction to Problem Statement

Given a string s and an integer k ( k<=s.length() ). Our task is to find the lexicographically largest string after removing exactly k characters from the given string.

### Sample Examples

Example 1:

``````Input: s = codingninjas, k = 2
Output: oingninjas``````

Example 2:

``````Input: s = chunmun, k = 3
Output: unun``````

To solve the above problem, we have to know about lexicographic order.

### What is lexicographic order

It simply means â€śdictionary order,â€ť i.e. the way in which the words are arranged in a dictionary.

The word which appeared later is said to be lexicographically larger than the word which appeared earlier in the dictionary. If we want to know from the two words which word will appear before the other, we compare the words letter by the letter starting from the first position.

For example, the word â€śrahulâ€ť will appear before (and considered lexicographically smaller) the word â€śramuâ€ť in the dictionary because the first two letters are the same, but the third letter in the word â€śrahulâ€ť is â€śhâ€ť, which is smaller than the third letter in the word â€śramuâ€ť which is â€śmâ€ť.

## Approach

The idea is simple, we create an empty res string and start traversing the string s.

If the res string is empty, we push the current character from string s in the res string.

We check for the last character of the res string if its ASCII value is smaller than the current character of the string s, we pop the last character while it is not empty, and after every removal, we reduce the value of k by 1 as we donâ€™t remove more than k characters.

Else we push the current character in the res string.

Finally, if we removed exactly k characters from the res string, i.e. k = 0,  return the res string. Else we remove the last k characters from the res string and return the res string.

Steps:

• Traverse the string s.
• We check for every character in string s; if the ASCII value of the last character of the res string is less than the current character of the string s, we remove the last character from the res string and reduce the value of k by 1.
• Now, we insert the current character from string s to res string.
• After complete traversal of string s, if k>0, we remove the last k characters from the res string as we need to remove exactly k characters.
• Return the res string, which is the required lexicographically largest string after removing k characters.

Example:

Input = chunmun, k= 3

Initially, s = chunmun, k = 3, res = â€śâ€ť

Steps:

• Push â€ścâ€ť in res string as res is empty, s[0] = c, res = c, k = 3.

• Now, remove â€ścâ€ť from the res string because the ASCII value of â€ścâ€ť is smaller than the current character in string s and reduce k by 1, s[1] = h, res = h, k = 2.

• Similarly, remove â€śhâ€ť and push â€śuâ€ť as the ASCII value of â€śhâ€ť is smaller than â€śuâ€ť and reduce k by 1,  s[2] = u, res = u, k = 1.

• Push â€śnâ€ť in res string because the last characterâ€™s ASCII value in res string is larger than â€śnâ€ť, s[3] = n, res = un, k = 1.

• Push â€śmâ€ť in res string, s[4] = m, res = unm, k = 1.

• Remove â€śmâ€ť from the res string and push â€śuâ€ť, which has more ASCII value than â€śmâ€ť and reduce k by 1, s[5] = u, res = unu, k = 0.

• Push â€śnâ€ť in the res string, s[5] = n, res = unun, k = 0.

Finally, return the res string, which is the required lexicographically largest string.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Implementation

Let us see the implementation of the discussed approach in C++, Java and Python.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

string lex_lrgst_Str(string s, int k)
{
string res;

for (int i = 0; i < s.length(); i++) {

while (res.length() > 0 && res.back() < s[i] && k > 0) {

res.pop_back();
k--;
}

res.push_back(s[i]);
}
while (res.length() > 0 && k > 0) {

res.pop_back();
k--;
}

return res;
}

int main()
{
int k;
string s;
cout << "Enter the string: " << endl;
cin >> s;
cout << "Enter the value of k: " << endl;
cin >> k;
cout << lex_lrgst_Str(s, k) << endl;
}``````

Output:

``````Enter the string:
codingninjas
Enter the value of k:
2
oingninjas``````

### Implementation in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static String largestString(String num, int k) {
String ans = "";

for (char i: num.toCharArray()) {

while (ans.length() > 0 && ans.charAt(ans.length() - 1) < i && k > 0) {
ans = ans.substring(0, ans.length() - 1);

k--;
}

ans += i;
}

while (ans.length() > 0 && k > 0) {
ans = ans.substring(0, ans.length() - 1);
k--;
}

return ans;
}
public static void main(String[] args) throws java.lang.Exception {
int k;
String s;

Scanner sc = new Scanner(System.in);
System.out.println("Enter the string: ");
s = sc.nextLine();

System.out.println("Enter the value of k: ");
k = sc.nextInt();

System.out.print(largestString(s, k) + "\n");
}
}``````

Output:

``````Enter the string:
codingninjas
Enter the value of k:
2
oingninjas``````

### Implementation in Python

``````def lex_lrgst_Str(s, k):
res = ""
for i in range(len(s)):
while(len(res) > 0 and res[-1] < s[i] and k > 0):
res = res[:-1]
k -= 1
res += s[i]
while(len(res) > 0 and k > 0):
res = res[:-1]
k -= 1
return res

s = str(input("Enter the string: "))
k = int(input("Enter the value of k: "))
print(lex_lrgst_Str(s, k))``````

Output:

``````Enter the string:
codingninjas
Enter the value of k:
2
oingninjas``````

### Complexity Analysis

Time complexity: O(n), where n is the length of the given string as we are traversing the given string.

Space complexity: O(n), as we are using an extra res string.

Also see, Euclid GCD Algorithm

1. Why do we use strings?
Strings are similar to sentences as they are made up of words. They're made up of a list of characters, or rather an "array of characters." When communicating information from the programme to the user, strings are extremely useful. When it comes to storing data for the computer, they are less useful.

2. What is the meaning of lexicographical order?
Alphabetical order is the lexicographical order. Numerical ordering is the other type. Take a look at the numbers 1, 10, and 2. Those values are listed in alphabetical order. In numerical order, 10 comes after 2, but in "alphabetical" order, 10 comes before 2.

3. What exactly is the knapsack algorithm?
The knapsack problem is a combinatorial optimisation problem that entails: Determine the number of each item included in a collection given a set of items, each with a weight and a value so that the total weight is less than or equal to a given limit and the total value is as large as possible.

## Key Takeaways

So, this article discussed the approach of finding the lexicographically largest string after removing exactly k characters from the string with an example for better understanding and its code in C++.

Also check out - Data Dictionary In Software Engineering

Recommended problems -

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free!