Lexicographically largest String after removal of K characters

Sandeep kamila
Last Updated: May 13, 2022

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.

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.

Frequently Asked Questions

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

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! 

Thank you for reading!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think