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
Input: 6 2 jacmie
Output: jmie
Dry Run
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
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.add(s[i]); } String st="";
for (char c : deq)
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 "+
  • Time Complexity: O(n).
  • Auxiliary Space: O(n).



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