Largest String after k deletions

Let the string s , be "ritz" . The number of characters to be erased , k , is 2 .
There are 6 possible ways of deleting two characters
from s: "ri" , "rt", "rz" , "it" , "iz" , "tz".
Among these strings "tz" is the largest in dictionary order.
Thus "tz" is the desired output.
Input: 6 2 jackie
Output: jkie
characters "a" and "c" are deleted
Input: 11 4 trtyfhdtsep
Output: yhdtsep
Example:
Input: 6 2 jacmie
Output: jmie
Dry Run
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.io.IOException;
public class Main
{
//function to find the largest string after deleting k characters

public static String largestString(int n , int k, String sc ) {
char[] s = sc.toCharArray();
// Deque dq used to find the largest string in dictionary
// after deleting k characters
Deque<Character> deq = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
//if dq is null , then only push character to dq
// and if the last element of deque is smaller than the
// current iterating character then pop the last element.
while (deq.size() > 0 && deq.getLast() < s[i] && k > 0) {
deq.pollLast();
k--;
}
deq.add(s[i]); } String st="";
for (char c : deq)
st=st+Character.toString(c);
return st;
}
// main function for input and for calling largestString
public static void main (String[] args) throws IOException{
int n = 9;
int k = 3;
String sc="xyvgfrtoa";
String result = largestString(n , k , sc);
System.out.println("The largest string in dictionary is "+
result);
}
}
  • Time Complexity: O(n).
  • Auxiliary Space: O(n).

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Port of Kubernetes v1.24.0 for illumos (and solaris)

Negative numbers representation

Data-in-Transit:BigQuery+Spark

Stalin Skin

VideoCoin Worker on Akash

10 GitHub Repos That Can Help You Grow as a Web Developer

How To Create Backend APIs Using Spring Boot?

How To Create Backend APIs Using Spring Boot

A Simple Introduction to ForgeRock Intelligent Authentication

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhinay Gupta

Abhinay Gupta

More from Medium

The Art Of Programming #9

Bubble Sort vs Selection Sort

Need of different Sorting Techniques

String Manipulation