Lexicographically largest String after removal of K characters

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

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

You can also try this code with Online C++ Compiler

Run Code

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");
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

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

You can also try this code with Online C++ Compiler

Run Code

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))

You can also try this code with Online Python Compiler

Run Code

Output:

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

You can also try this code with Online C++ Compiler

Run Code

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

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

Also check out - Data Dictionary In Software Engineering

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

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!