Java: Remove duplicate letters and arrange in lexicographical order

Java Basic: Exercise-200 with Solution

Write a Java program to remove duplicate letters and arrange them in lexicographical order from a given string containing only lowercase letters.

Note: In mathematics, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters.

Pictorial Presentation:

Sample Solution:

Java Code:

import java.util.*;
import java.lang.*;
public class Solution {
 public static void main(String[] args) {
  String str = "zxywooxz";
  System.out.print("Original string: " + str);
  System.out.print("\nAfter removing duplicate characters: " + remove_duplicate_letters(str));
 }
 public static String remove_duplicate_letters(String str1) {
  int[] ctr = new int[26];
  boolean[] in_stack = new boolean[26];
  char[] st_char = new char[str1.length()];
  int len = 0;

  for (char c: str1.toCharArray()) {
   ctr[c - 'a']++;
  }

  for (char c: str1.toCharArray()) {
   ctr[c - 'a']--;

   if (!in_stack[c - 'a']) {
    while (len > 0 && c < st_char[len - 1] && ctr[st_char[len - 1] - 'a'] > 0) {
     in_stack[st_char[--len] - 'a'] = false;
    }
    st_char[len++] = c;
    in_stack[c - 'a'] = true;
   }
  }
  return new String(st_char, 0, len);
 }
}

Sample Output:

Original string: zxywooxz
After removing duplicate characters: xywoz

Flowchart:

Java Code Editor:

Company:  Google

Contribute your code and comments through Disqus.

Previous: Write a Java program to check a string follows a given pattern.
Next: Write a Java program to divide a given array of integers into given k non-empty subsets whose sums are all equal. Return true if all sums are equal otherwise return false.