Lexicographically Smallest String By Deleting Duplicate Characters

bcabc
You need delete 1 ‘b’ and 1 ‘c’, so you delete the first ‘b’ and first ‘c’, the new string will be abc which is smallest.
PS: If you try to use greedy algorithm to solve this problem, you must make sure that you could pass this case: ​
cbacdcbc. answer is acdb not adcb.

//smallest lexicographic string after removing duplicates 
public static String lexicoSmallNoDuplicates(String str){
	int[] hist = new int[256];
	StringBuilder out = new StringBuilder();
	
	//compute character count histogram
	for(int i = 0; i<str.length(); i++){
		hist[str.charAt(i)-'0']++;
	}
	
	//scan left to right and remove current if and only if - 
	//count for cur character is > 1 and value of character is lexicographically 
	//greater than next character. Otherwise we take the character (if not already taken early)
	for(int i = 0; i<str.length()-1; i++){
		int cur = str.charAt(i)-'0';
		int next = i == str.length()-1 ? Integer.MAX_VALUE : str.charAt(i+1)-'0';
		if(cur > next && hist[cur] > 1){
			hist[cur]--;
		}
		else if(hist[cur] != 0){
			out.append(str.charAt(i));
			hist[cur] = 0;
		}
	}
	
	return out.toString();
}

Leave a Reply

Your email address will not be published. Required fields are marked *