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




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

Recommended from Medium

Hands-On! Postman/Newman CI/CD Integration

New features to watch out for in the Android 12 developer preview

How To Learn A Programming Language in One Day

Python: Any() Function Tutorial

Coroutine in Android: Working with Lifecycle

Changing the User Interface when the state changes in Flutter

RhoMobile Suite for Mobile App development

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

Should I make class member variables const or constexpr?

Crash Course: Bubble sort.


All you need to know about Recursion