# 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 jackieOutput:jkie

characters "a" and "c" are deletedInput:11 4 trtyfhdtsepOutput: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

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