Largest String after k deletions

Given a string of length n, return the largest string based on dictionary order, that can be obtained by erasing k characters from that string.

For two strings, x and y, each consisting of n characters, x is larger than y, based on dictionary order, when the first i-1 letters in x and y are equal, where 1<= i <=n, but the ith letter in x is larger than ith in y. For example, “caa” is larger than “baa” and “abza” is larger than “abqa”.

Consider the following example:

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

Method 1 : Brute Force

Find all the subsequence of length m=n-k and store them in a list.

There will be nCm such sequences. Now we will find the largest one.

Time Complexity would be O((nCm)*n)

Method 2 : Using ArrayDeque

The approach is to use ArrayDeque. We will store the character in the deque and if the last character in the deque is smaller than the current character, then we will pop the last character from deque and decrease k , and add the current character to deque.

Example:
Input: 6 2 jacmie 
Output: jmie

Dry Run

Code:

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

Complexity Analysis:

• Time Complexity: O(n).
• Auxiliary Space: O(n).