Pintu Engineering Logic Test #2

README.md

Jade love uniqueness. Every time he found a string, he makes that string into multiple unique character strings. But Jade has a rule to make a new string, you can only remove the duplicate character, and cannot change the arrangement of the characters. Jade also sort the possibilities of the string in lexicographic order.

We consider lexicographic order of characters as their order of ASCII value. Hence the lexicographical order of character will be 'a', 'b', 'c', ..., 'y', 'z'.

For example:
string "sebaerb"

Possible arragements:

• saerb -> the first in lexicographical order
• sbaer -> the 2nd in lexicographical order
• searb -> the 3rd in lexicographical order
• sebar -> the first occurence from left to right, the last in lexicographical order

For following question:
Given a string
https://gist.github.com/Jekiwijaya/0b85de3b9ff551a879896dd78256e9b8

UniqueString.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class UniqueString {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine();
    System.out.println(solveFirstOccurence(input));
    System.out.println(solveLexicographically(input));
  }

  public static String solveFirstOccurence(String input) {
    // Simple solution, just pick the char if it hasn't shown up before.
    StringBuilder result = new StringBuilder();
    boolean[] occurence = new boolean[256];  // ASCII size
    for (int i = 0; i < input.length(); i++) {
      char c = input.charAt(i);
      if (!occurence[c]) {
        result.append(c);
        occurence[c] = true;
      }
    }
    return result.toString();
  }

  public static String solveLexicographically(String input) {
    StringBuilder result = new StringBuilder();
    boolean[] occurence = new boolean[256];
    for (int i = 0; i < input.length(); i++) {
      char c = input.charAt(i);
      if (!occurence[c]) {
        result.append(c);
        occurence[c] = true;
      } else {
        // Find the index of the previous occurence of the character in the result string.
        int existingIdx = result.indexOf(String.valueOf(c));
        // If the next char after the previous occurence is smaller than the current character,
        // removing the previous occurence (and using the current occurence instead) will make
        // the result string smaller lexicographically.
        if (existingIdx + 1 < result.length() && result.charAt(existingIdx + 1) < c) {
          result.deleteCharAt(existingIdx);
          result.append(c);
        }
      }
    }
    return result.toString();
  }
}