Remove Duplicate Letters [LeetCode]

Problem Description

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 "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solutions
In my personal opinion, this problem is kinda interesting.

I. Simple Solution - O(kN) 
(Where k is the total number of distinct characters, N is length of the original string)

My first question after reading the problem description is that: What is the first character of the possible result? Can I determine it?

Yes, we can determine by an observation. If we call totalChars is the total number of distinct characters in the string. Then the required result must have a length of totalChars.  

Furthermore, its first character must be the smallest among all possible candidates. So what is a possible candidate? We easily see that a character is able to be the first character in a possible result string must have (totalChars - 1) distinct characters staying behind it in the original string.

For example, given s="bcabc", there are possible results "bca", "cab", "abc". We see that b=s[0] has 2 = totalChars-1 distinct characters behind it "a", "c". Similarly with c=s[1] and a=s[2]. Among these 3 possible candidates,  a=s[2] is the smallest. If there are 2 possible candidates with the same character, we just pick the one with smaller position.

Now after getting the first character of the result, what we do next? We can eliminate that character from the original string (by marking it as assigned). Then we repeat the process for the rest of characters!

Below is the java code.

public class Solution {

    public int ASSIGNED = -1;
    public int UNTOUCHED = 0;
    public int TOUCHED = 1;
    public char LARGE_CHAR = (char) 127;
    public String removeDuplicateLetters(String s){
        int n = s.length();
        if(n == 0) return s;
        
        //We use 128 is to avoid substraction
        //if we use 26, we have to substract 'a' from a char
        int[] status = new int[128];
        
        char c, smallestChar;
        int totalChars = 0;
        
        for(int i=0; i<n; i++){
            c = s.charAt(i);
            if(status[c] == UNTOUCHED) totalChars++;
            status[c] = TOUCHED;
        }
        
        StringBuilder bd = new StringBuilder();
        int tt = -1; //temp variable
        int last = -1; //last position of char that was assigned
        
        for(int i=totalChars; i>0; i--){
            smallestChar = LARGE_CHAR;
            totalChars = 0;
            
            //reset the status array
            for(int j='a'; j<='z'; j++) 
                if (status[j] == TOUCHED) status[j] = UNTOUCHED;
            
            //choose the smallest candiate by running backward
            for(int j=n-1; j>last; j--){
                c = s.charAt(j);
                if(status[c] == ASSIGNED) continue;
                if(status[c] == UNTOUCHED)totalChars++;
                
                if(totalChars == i) {
                    if(c <= smallestChar){
                        smallestChar = c;
                        tt = j;
                    }
                }
                status[c] = TOUCHED;
            }
            
            status[smallestChar] = ASSIGNED; //marked as assigned
            last = tt;
            bd.append(smallestChar);
        }
        
        return bd.toString();
    }
}

II. Better Solution - O(hN)
(Where h is a number between 1 and the total number of distinct characters)

After coming up with the above solution, I mumble "smallest candidates, smallest char, smallest possible, smallest..." . Yes, in that solution, we tried to find a smallest single character, why don't we try to find a smallest set of characters? Let's go on that direction!

We call a candidate set is a subset of distinct characters from 0 to i in the original string s so that there are still enough available characters from (i+1) to the end of string to make up totalChars distinct character.

Let's consider s="bcabc", at position 0, the candidate set is {b}. At 1, the candidate sets are {b}, {c}, {b,c}. At 2, the candidate sets are {b}, {c}, {a}, {b,c}, {c,a}, {b,c,a}. And our purpose is the same: find the smallest candidate set (by smallest, we mean lexicographically smallest). I.e, At 1, smallest candidate set is obviously {b}, at 1 it is {b}, and at 2 is {a}.

Suppose at position i, we have the smallest candidate set {a0,a1,..., ak}. Now at position i+1, what is the smallest candidate set? We know that {a0,a1,..., ak} are distinct. 

If s[i+1] already in {a0,a1,..., ak}, is it possible that there is a subset {ai0, ai1, ..., aij} so that  {ai0, ai1, ..., aij, s[i+1]} < {a0,a1,..., ak} is also a candidate set? If yes, we can easily see that {ai0, ai1, ..., aij} is a candidate set at position i, and {ai0, ai1, ..., aij} < {a0,a1,..., ak} . This means that {a0,a1,..., ak} is not the smallest candidate set at position i. Therefore, we don't need to care if s[i+1] is already in the candidate set (or we call it "assigned").

Now, if s[i+1] is not "assigned",  we have the same question - is it possible that there is a subset {ai0, ai1, ..., aij} so that  {ai0, ai1, ..., aij, s[i+1]} < {a0,a1,..., ak} is also a candidate set? If ak > s[i+1], and there are still characters that equals ak after i+1, we can remove ak and check again with ak-1; if there is no more, replace it by s[i+1]. If ak < s[i+1], we cannot replace ak by s[i+1]. So we just simply add s[i+1] to the set. Simply enough?

And to represent the smallest candidate set, we can use linked list, or array. Below are 2 different implementations.

a) Using Linked List (also by array ^_^)

public class Solution {

    public static char START = (char)('a'-1);
    public String removeDuplicateLetters(String s){
        if(s.length() == 0) return s;
        
        //We use 128 is to avoid substraction
        //if we use 26, we have to substract 'a' from a char
        int[] count = new int[128];
        char[] prev = new char[128];
        boolean[] assigned = new boolean[128];
        char c;
        char end = START;
        
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            count[c]++;
        }
        
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            count[c]--;
            if(assigned[c])
                continue;
                
            while(end >= c && count[end]>0){
                assigned[end] = false;
                end = prev[end];
            }
            
            prev[c] = end;
            end = c;
            assigned[c] = true;
        }
        
        StringBuilder bd = new StringBuilder();
        while(end>START){
            bd.append(end);
            end = prev[end];
        }
        return bd.reverse().toString();
    }
}

b) Using array (which similar to stack)

public class Solution {

    public String removeDuplicateLetters(String s){
        if(s.length() == 0) return s;
        
        //We use 128 is to avoid substraction
        //if we use 26, we have to substract 'a' from a char
        int[] count = new int[128];
        char[] result = new char[26];
        boolean[] assigned = new boolean[128];
        char c;
        int end = -1;
        
        for(int i=0; i<s.length(); i++){
            count[s.charAt(i)]++;
        }
        
        for(int i=0; i<s.length(); i++){
            c = s.charAt(i);
            count[c]--;
            if(assigned[c])
                continue;
                
            while(end >= 0 && result[end] > c && count[result[end]]>0){
                assigned[result[end]] = false;
                end--;
            }
            
            end++;
            result[end] = c;
            assigned[c] = true;
        }
        
        StringBuilder bd = new StringBuilder();
        for(int i=0; i<=end; i++){
            bd.append(result[i]);
        }
        return bd.toString();
    }
}

Integer to English Words [LeetCode]

Problem Description

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Solution
To solve it, we divide the input number into chunks so that each has 3 digits.
One note about this LeetCode problem is that some edge cases such as "101" is considered as "One Hundred One" instead of "One Hundred And One". So this should not be correct in real life application!

I. Java Solution

public class Solution {
    
    String[] map1 = new String [] {"", " One", " Two", " Three", " Four", " Five", 
            " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", 
            " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", 
            " Eighteen", " Nineteen" };
            
    String[] map2 = new String[] {"", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", 
        " Seventy", " Eighty", " Ninety" };
        
    String[] map3 = new String[] {"", " Thousand", " Million", " Billion" };
    final String HUNDRED = " Hundred";
    
    public String threeDigitToWords(int num){
        String result = "";
        if (num > 99){
            result = map1[num / 100] + HUNDRED;
        }
        num %= 100;
        if(num < 20){
            result +=  map1[num];
        }else {
            result += map2[num/10] + map1[num%10];
        }
        return result;
    }
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        String result = "";
        
        int i = 0; //check if it is thousand, million, billion
        while(num != 0){
            if(num % 1000 != 0)
                result = threeDigitToWords(num % 1000) + map3[i] + result;
            i++;
            num /= 1000;
        }
        return result.trim();
    }
}

II. Python Solution

class Solution(object):
    def __init__(self):
        self.map1 = ["", " One", " Two", " Three", " Four", " Five", 
            " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", 
            " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", 
            " Eighteen", " Nineteen" ]
            
        self.map2 = ["", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", 
            " Seventy", " Eighty", " Ninety" ]
            
        self.map3 = ["", " Thousand", " Million", " Billion"]
        self.HUNDRED = " Hundred"
        
    def threeDigitToWords(self, num):
        result = ""
        if num > 99 : 
            result = self.map1[num / 100] + self.HUNDRED

        num %= 100
        if num < 20:
            result +=  self.map1[num]
        else:
            result += self.map2[num/10] + self.map1[num%10]
        
        return result
    
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num == 0: return "Zero"
        result = ""
        
        i = 0 #check if it is thousand, million, billion
        while num != 0:
            if num % 1000 != 0:
                result = self.threeDigitToWords(num % 1000) + self.map3[i] + result
            i+=1
            num /= 1000
        
        return result[1:];

Appendix B: Pythonic Solution
Below is the short pythonic code.

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        def make_lists(s): return [[]] + [[i] for i in s.split()]
        
        under20 =  make_lists('One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen')
        tens = [[]] + make_lists('Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety')
        thousands =  make_lists("Thousand Million Billion")
        
        def threeDigitToWords(n):
            return (under20[n/100] + ['Hundred'] if n>99 else []) + tens[n%100/10] + (under20[n%100] if n%100 < 20 else under20[n%100%10])
            
        def toWords(n,i):
            return (toWords(n/1000,i+1) if n else []) + threeDigitToWords(n%1000) + (thousands[i] if n%1000 else [])  
        
        return ' '.join(toWords(num,0)) or 'Zero'

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        Credited: LeetCode
        """
        under20 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
        tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
        def find_words(n):
            if n < 20:
                return under20[n-1:n]
            if n < 100:
                return [tens[n/10-2]] + find_words(n%10)
            if n < 1000:
                return [under20[n/100-1]] + ['Hundred'] + find_words(n%100)
            for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
                if n < 1000**(p+1):
                    return find_words(n/1000**p) + [w] + find_words(n%1000**p)
        return ' '.join(find_words(num)) or 'Zero'

Valid Parentheses

Problem Description

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution

This is an easy solution using stack.

class Solution:
    # @param {string} s
    # @return {boolean}
    def isValid(self, s):
        dic = {')':'(', '}':'{', ']':'['}
        stack = []
        for p in s:
            if p not in dic:
                stack.append(p)
            elif not stack or dic[p] != stack.pop(-1):
                return False
        return not stack

Longest Palindromic Substring : From simple to complex solutions

Problem Description
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Solution
I. Simple solution with expansion from an Index

For each index, we can try to expand as much as possible so that the substring is still palindromic. However, this is O(N^2) time complexity.

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <= 1) return s;
        int start = 0, maxLength = 1;
        for(int i = 0; i<s.length();){
            if(s.length() - i <= maxLength/2) break;
            int j = i, k = i;
            while(k < s.length() - 1 && s.charAt(k+1) == s.charAt(k)) ++k;
            i = k + 1;
            while(k < s.length() - 1 && j > 0 && s.charAt(k+1) == s.charAt(j-1)) {++k; --j; }
            int l = k-j+1;
            if(l > maxLength) {maxLength = l; start = j;}
        }
        return s.substring(start, start + maxLength);
    }
}

II. Manacher Algorithm in Linear time

If you are not familiar with Manacher algorithm, you can read more on this wiki article .

import java.util.Arrays;

public class Solution {
    
    public static String longestPalindrome(String s) {
        if (s==null || s.length()==0)
            return "";
        
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length]; 
        int c = 0, r = 0; // Here the first element in s2 has been processed.
        int m = 0, n = 0; // The walking indices to compare if two elements are the same
        for (int i = 1; i<s2.length; i++) {
            if (i>r) {
                p[i] = 0; m = i-1; n = i+1;
            } else {
                int i2 = c*2-i;
                if (p[i2]<(r-i)) {
                    p[i] = p[i2];
                    m = -1; // This signals bypassing the while loop below. 
                } else {
                    p[i] = r-i;
                    n = r+1; m = i*2-n;
                }
            }
            while (m>=0 && n<s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
            }
            if ((i+p[i])>r) {
                c = i; r = i+p[i];
            }
        }
        int len = 0; c = 0;
        for (int i = 1; i<s2.length; i++) {
            if (len<p[i]) {
                len = p[i]; c = i;
            }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
    }
 
    private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
            return "||".toCharArray();

        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i<(cs2.length-1); i = i+2) {
            cs2[i] = '|';
            cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
    }

    private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length<3)
            return "".toCharArray();

        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i<cs2.length; i++) {
            cs2[i] = cs[i*2+1];
        }
        return cs2;
    }    
}

III. Gusfield's Algorithm

This is an algorithm by Gusfield. If you want to learn more about string algorithm, take a look at Gusfield's course here.

public class Solution {
    char[] temp; 
    public int match(int a, int b,int len){ 
        int i = 0; 
        while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++; 
        return i; 
    }
    
    public String longestPalindrome(String s) {
        
        //This makes use of the assumption that the string has not more than 1000 characters.
        temp=new char[1001*2];
        int[] z=new int[1001 * 2];
        int L=0, R=0;
        int len=s.length();
    
        for(int i=0;i<len*2+1;i++){
            temp[i]='.';
        }
    
        for(int i=0;i<len;++i){
            temp[i*2+1] = s.charAt(i);
        }
    
        z[0]=1;
        len=len*2+1;
    
        for(int i=0;i<len;i++){
            int ii = L - (i - L);   
            int n = R + 1 - i;
            if (i > R)
            {
                z[i] = match(i, i,len);
                L = i;
                R = i + z[i] - 1;
            }
            else if (z[ii] == n)
            {
                z[i] = n + match(i-n, i+n,len);
                L = i;
                R = i + z[i] - 1;
            }
            else
            {
                z[i] = (z[ii]<= n)? z[ii]:n;
            } 
        }
    
        int n = 0, p = 0;
        for (int i=0; i<len; ++i)
            if (z[i] > n)
                n = z[p = i];
    
        StringBuilder result=new StringBuilder();
        for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
            if(temp[i]!='.')
                result.append(String.valueOf(temp[i]));
    
        return result.toString();
    }
}

Longest Consecutive Sequence: Some different approaches.

Problem Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solutions
I. Intuitive Solution

For each element e we check that if e is visited . If not, we check the length of the sequence ends at e-1, and length of the sequence starts at e+1, then combine these 2 sequence. (Note that we only update the 2 ends of the sequence). The following solution using 3 HashMap !!! To see why the "visited" HashMap needed, you can check on the following test case:
[-6,8,-5,7,-9,-1,-7,-6,-9,-7,5,7,-1,-8,-8,-2,0]
Take your time! ^_^

public class Solution {
    public int longestConsecutive(int[] nums) {
        int maxLength = 0;
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
        int left, right, l;
        for(int i = 0; i < nums.length; i++){
            if(visited.containsKey(nums[i])) continue;
            visited.put(nums[i], true);
            left = right = nums[i];
            if(map1.containsKey(nums[i]-1)) 
                left -= map1.get(nums[i]-1);
            if(map2.containsKey(nums[i] + 1))
                right += map2.get(nums[i]+1);
            l = right - left + 1;
            if(maxLength < l) maxLength = l;
            
            map1.put(right, l);
            map2.put(left, l);
        }
        return maxLength;
    }
}

II. Improvement on the code

With the above code, we can reduce the space to only 1 HashMap.

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i < num.length;i++){
            // if there is no duplicates, these two lines can be commented
            if(map.containsKey(num[i])) continue;
            map.put(num[i],1);

            int end = num[i];
            int begin = num[i];
            if(map.containsKey(num[i]+1))
                end = num[i] + map.get(num[i]+1);
            if(map.containsKey(num[i]-1))
                begin = num[i] - map.get(num[i]-1);
            longest = Math.max(longest, end-begin+1);
            map.put(end, end-begin+1);
            map.put(begin, end-begin+1);
        }
        return longest;
    }
}

III. The same idea as the II) approach can be expressed as the following code:

public class Solution {
    public int longestConsecutive(int[] num) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n : num) {
            if (!map.containsKey(n)) {
                int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
                int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
                // sum: length of the sequence n is in
                int sum = left + right + 1;
                map.put(n, sum);
    
                // keep track of the max length 
                res = Math.max(res, sum);
    
                // extend the length to the boundary(s)
                // of the sequence
                // will do nothing if n has no neighbors
                map.put(n - left, sum);
                map.put(n + right, sum);
            }
            else {
                // duplicates
                continue;
            }
        }
        return res;
    }
}

IV. Better solution

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i< num.length; i++){
            map.put(num[i], false);
        }
        
        int l, k;
        for(int i = 0;i < num.length;i++){
            
            if(map.containsKey(num[i]-1) || map.get(num[i])) continue;
            map.put(num[i], true);
            l = 0; k = num[i];
            while (map.containsKey(k)){
                l++;
                k++;
            }
            if(longest < l) longest = l;
            
        }
        return longest;
    }
}