Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given

Return

`"bcabc"`

Return

`"abc"`

Given

Return

`"cbacdcbc"`

Return

`"acdb"`

**Understand the problem:**

https://leetcode.com/discuss/73777/easy-to-understand-iterative-java-solution

The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":

- find out the last appeared position for each letter; c - 7 b - 6 a - 2 d - 4
- find out the smallest index from the map in step 1 (a - 2);
- the first letter in the final result must be the smallest letter from index 0 to index 2;
- repeat step 2 to 3 to find out remaining letters.

- the smallest letter from index 0 to index 2: a
- the smallest letter from index 3 to index 4: c
- the smallest letter from index 4 to index 4: d
- the smallest letter from index 5 to index 6: b

so the result is "acdb"

Notes:

- after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
- in step 3, the beginning index of the search range should be the index of previous determined letter plus one

**Code (Java):**

public class Solution { public String removeDuplicateLetters(String s) { if (s == null || s.length() <= 1) { return s; } // Step 1: find the last index for each char Map<Character, Integer> lastIndexMap = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); lastIndexMap.put(c, i); } // Step 2: for each character, find the smallest index in the map // Then find out the smallest char before the index. StringBuilder sb = new StringBuilder(); int start = 0; int end = findSmallestIndex(lastIndexMap); while (!lastIndexMap.isEmpty()) { char curr = 'z' + 1; int index = 0; for (int i = start; i <= end; i++) { char c = s.charAt(i); if ((c < curr) && (lastIndexMap.containsKey(c))) { curr = c; index = i; } } // append result sb.append(curr); lastIndexMap.remove(curr); // update the start and end start = index + 1; end = findSmallestIndex(lastIndexMap); } return sb.toString(); } private int findSmallestIndex(Map<Character, Integer> lastIndexMap) { int result = Integer.MAX_VALUE; for (int index : lastIndexMap.values()) { result = Math.min(result, index); } return result; } }

## No comments:

## Post a Comment