Leetcode 791. Custom Sort String

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :
Input: 
S = "cba"
T = "abcd"
Output: "cbad"
Explanation: 
"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

• S has length at most 26, and no character is repeated in S.
• T has length at most 200.
• S and T consist of lowercase letters only.

Code (Java):

class Solution {
    public String customSortString(String S, String T) {
        if (S == null || S.length() == 0) {
            return T;
        }

        // step 1: do the word for the T
        //
        int[] counts = new int[26];
        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            counts[c - 'a']++;
        }

        // step 2: reconstruct the result
        //
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            while (counts[c - 'a'] > 0) {
                sb.append(c);
                counts[c - 'a']--;
            }
        }

        for (int i = 0; i < 26; i++) {
            while (counts[i] > 0) {
                sb.append((char)(i + 'a'));
                counts[i]--;
            }
        }
    
        return sb.toString();
    }
}

Leetcode 788. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X.  Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

• N  will be in range [1, 10000].

Solution:
The problem can be solved by using dp. 
dp[i] = 0 means the number i is not good
dp[i] = 1 means the number is rotated to itself.
dp[i] = 2 means the number is rotated to the different number, so it's a good number. 

Code (Java):

class Solution {
    public int rotatedDigits(int N) {
        int[] dp = new int[N + 1];
        int count = 0;
        for (int i = 0; i <= N; i++) {
            if (i < 10) {
                if (i == 0 || i == 1 || i == 8) {
                    dp[i] = 1;
                } else if (i == 2 || i == 5 || i == 6 || i == 9) {
                    dp[i] = 2;
                    count++;
                }
            } else {
                int a = dp[i / 10];
                int b = dp[i % 10];
                if (a == 1 && b == 1) {
                    dp[i] = 1;
                } else if ((a == 1 && b == 2) || (a == 2 && b >= 1)) {
                    dp[i] = 2;
                    count++;
                }
            }
        }

        return count;
    }
}

Leetcode 772. Basic Calculator III

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.

Code (Java):

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // remove leading and trailing spaces and white spaces.
        //
        s = s.trim().replaceAll("[ ]+", "");

        if (s == null || s.length() == 0) {
            return 0;
        }

        Stack<Character> opStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();

        int i = 0;
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + Character.getNumericValue(s.charAt(i));
                    i++;
                }
                numStack.push(num);
            } else {
                char op = s.charAt(i);
                if (opStack.isEmpty()) {
                    opStack.push(op);
                    i++;
                } else if (op == '+' || op == '-') {
                    char top = opStack.peek();
                    if (top == '(') {
                        opStack.push(op);
                        i++;
                    } else {
                        calculate(numStack, opStack);
                    }
                } else if (op == '*' || op == '/') {
                    char top = opStack.peek();
                    if (top == '(') {
                        opStack.push(op);
                        i++;
                    } else if (top == '*' || top == '/') {
                        calculate(numStack, opStack);
                    } else if (top == '+' || top == '-') {
                        opStack.push(op);
                        i++;
                    }
                } else if (op == '(') {
                    opStack.push(op);
                    i++;
                } else if (op == ')') {
                    while (opStack.peek() != '(') {
                        calculate(numStack, opStack);
                    }
                    opStack.pop();
                    i++;
                }
            }
        }

        while (!opStack.isEmpty()) {
            calculate(numStack, opStack);
        }

        return numStack.peek();
    }
    
    private void calculate(Stack<Integer> numStack, Stack<Character> opStack) {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        
        char op = opStack.pop();
        
        int ans = 0;
        
        switch(op) {
            case '+':
                ans = num1 + num2;
            break;
            case '-':
                ans = num1 - num2;
            break;
            case '*':
                ans = num1 * num2;
            break;
            case '/':
                ans = num1 / num2;
            break;
        }
        
        numStack.push(ans);
    }
}

Leetcode 767. Reorganize String

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

Note:

• S will consist of lowercase letters and have length in range [1, 500].

Solution:
use a priority queue.

Code (Java):

class Solution {
    public String reorganizeString(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        // step 1: check word count for each char
        //
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts[c - 'a']++;

            if (counts[c - 'a'] > (int)Math.ceil((double)s.length() / 2)) {
                return "";
            }
        }

        // step 2: put the count into a pq
        //
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>(new MyPairComparator());
        for (int i = 0; i < counts.length; i++) {
            Pair pair = new Pair(counts[i], (char)(i + 'a'));
            pq.offer(pair);
        }

        // construct the result
        //
        StringBuilder sb = new StringBuilder();
        while (sb.length() < s.length()) {
            Pair pair = pq.poll();
            if (sb.length() == 0 || sb.charAt(sb.length() - 1) != pair.c) {
                sb.append(pair.c);
                pair.count--;
                //if (pair.count > 0) {
                    pq.offer(pair);
                //}
            } else {
                // pull the head and get the second biggest
                //
                Pair sec = pq.poll();
                sb.append(sec.c);
                sec.count--;
                //if (sec.count > 0) {
                    pq.offer(sec);
                //}
                pq.offer(pair);
            }
        }

        return sb.toString();
    }
}


class Pair {
    int count;
    char c;

    public Pair (int myCount, char myChar) {
        count = myCount;
        c = myChar;
    }
}

class MyPairComparator implements Comparator<Pair> {
    public int compare(Pair a, Pair b) {
        return b.count - a.count;
        
    }
}

Update on 5/23/19

/*
 * @lc app=leetcode id=767 lang=java
 *
 * [767] Reorganize String
 */
class Solution {
    public String reorganizeString(String S) {
        if (S == null || S.length() == 0) {
            return "";
        }

        // step 1: do the word count
        int[] counts = new int[26];
        for (int i = 0 ; i < S.length(); i++) {
            char c = S.charAt(i);
            counts[c - 'a'] += 1;
        }

        // step2: sort the word count 
        PriorityQueue<Pair> pq = new PriorityQueue<>(new MyPairComparator());
        
        for (int i = 0; i < 26; i++) {
            if (counts[i] == 0) {
                continue;
            }
            Pair pair = new Pair((char)(i + 'a'), counts[i]);
            pq.offer(pair);
        }

        if (pq.peek().count > (S.length() + 1) / 2) {
            return "";
        }

        StringBuilder ans = new StringBuilder();
        while (!pq.isEmpty()) {
            Pair top = pq.poll();
            if (ans.length() > 0 && top.c == ans.charAt(ans.length() - 1)) {
                Pair secondTop = pq.poll();
                pq.offer(top);
                top = secondTop;
            }

            ans.append(top.c);
            top.count -= 1;

            if (top.count > 0) {
                pq.offer(top);
            }
        }

        return ans.toString();
    }
}

class Pair {
    char c;
    int count;
    public Pair(char c, int count) {
        this.c = c;
        this.count = count;
    }
}

class MyPairComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair a, Pair b) {
        return b.count - a.count;
    }
}

Leetcode 758. Bold Words in String

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b>tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d". Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Note:

1. words has length in range [0, 50].
2. words[i] has length in range [1, 10].
3. S has length in range [0, 500].
4. All characters in words[i] and S are lowercase letters.

Code (Java):

class Solution {
    public String boldWords(String[] words, String S) {
        if (words == null || words.length == 0) {
            return S;
        }

        // step 1: find start and end pos of the substring
        //
        List<Interval> intervals = new ArrayList<>();
        for (String t : words) {
            strStr(S, t, intervals);
        }
        
        if (intervals.isEmpty()) {
            return S;
        }

        // step 2: sort the intervals based on the start index
        //
        Collections.sort(intervals, new IntervalComparator());

        // step 3: merge intervals
        //
        List<Interval> mergedIntervals = mergeIntervals(intervals);

        // step 4: compose the result based on the merged intervals
        //
        StringBuilder sb = new StringBuilder();
        int prev = 0;
        
        for (int i = 0; i < mergedIntervals.size(); i++) {
            Interval curr = mergedIntervals.get(i);
            // prev seg
            //
            sb.append(S.substring(prev, curr.start));
            sb.append("<b>");
            
            // curr seg
            //
            sb.append(S.substring(curr.start, curr.end + 1));
            sb.append("</b>");
            
            prev = curr.end + 1;
        }
        
        // trailing substring
        //
        if (prev < S.length()) {
            sb.append(S.substring(prev));
        }

        return sb.toString();
    }

    private void strStr(String s, String t, List<Interval> list) {
        for (int i = 0; i < s.length() - t.length() + 1; i++) {
            int j = 0;
            while (j < t.length()) {
                if (s.charAt(i + j) == t.charAt(j)) {
                    j++;
                } else {
                    break;
                }
            }

            if (j == t.length()) {
                Interval interval = new Interval(i, i + j - 1);
                list.add(interval);
            }
        }
    }

    private List<Interval> mergeIntervals(List<Interval> intervals) {
        List<Interval> ans = new ArrayList<>();
        
        if (intervals == null || intervals.isEmpty()) {
            return ans;
        }

        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev.end >= curr.start || prev.end + 1 == curr.start) {
                prev.end = Math.max(prev.end, curr.end);
            } else {
                ans.add(new Interval(prev.start, prev.end));
                prev = curr;
            }
        }

        ans.add(prev);

        return ans;
    }
}

class Interval {
        int start;
        int end;

        public Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval a, Interval b) {
        return a.start - b.start;
    }
}

Leetcode 696. Count Binary Substrings

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.

s will only consist of "0" or "1" characters.

Code (Java):

class Solution {
    public int countBinarySubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int prev = 0;
        int curr = 1;

        int ans = 0;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curr++;
            } else {
                ans += Math.min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }

        ans += Math.min(prev, curr);

        return ans;
    }
}

Leetcode 686. Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.

Code (Java):

class Solution {
    public int repeatedStringMatch(String A, String B) {
        if (A == null || A.length() == 0) {
            return -1;
        }

        if (B == null || B.length() == 0) {
            return 0;
        }

        // step 1: calculate the min number of steps since lenA >= lenB
        //
        int count = 0;
        StringBuilder sb = new StringBuilder();

        while (sb.length() <= B.length() + A.length()) {
            if (sb.toString().contains(B)) {
                break;
            } else {
                sb.append(A);
                count++;
            }
        }

        if (sb.toString().contains(B)) {
            return count;
        } else {
            return -1;
        }
    }
}

Discussion:
Why we need to check sb().length <= A.length() + B.length()? There is one corner case
A = abc
B = cabcacbc

The expected answer is 4. 

If we just stop when sb.length() > B.length(), we may miss one more step.  

Leetcode 681. Next Closest Time

Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

Code (Java):

class Solution {
    public String nextClosestTime(String time) {
        int original = getElapsedMinutes(time);
        int minDiff = Integer.MAX_VALUE;
        int ans = original;

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < time.length(); i++) {
            if (time.charAt(i) != ':') {
                set.add(Character.getNumericValue(time.charAt(i)));
            }
        }

        for (int h1 : set) {
            for (int h2 : set) {
                if (h1 * 10 + h2 < 24) {
                    for (int m1 : set) {
                        for (int m2 : set) {
                            if (m1 * 10 + m2 < 60) {
                                int currTime = (h1 * 10 + h2) * 60 + (m1 * 10 + m2);
                                int diff = Math.floorMod(currTime - original, 24 * 60);
                                if (diff > 0 && diff < minDiff) {
                                    ans = currTime;
                                    minDiff = diff; 
                                }
                            }
                        }
                    }
                }
            }
        }

        return String.format("%02d:%02d", ans / 60, ans % 60);
    }
    
    private int getElapsedMinutes(String time) {
        int hour = Character.getNumericValue(time.charAt(0)) * 10 + Character.getNumericValue(time.charAt(1));
        int min = Character.getNumericValue(time.charAt(3)) * 10 + Character.getNumericValue(time.charAt(4));
        
        return hour * 60 + min;
    }
}

Discussion:
One corner case to consider is if the time is 11:11, the next time should be 11:11 as it's for next day. But int the code since we check diff > 0, the ans will return 0. To handle this case, the initial value should be original time.

Leetcode 678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

Intuition

When checking whether the string is valid, we only cared about the "balance": the number of extra, open left brackets as we parsed through the string. For example, when checking whether '(()())' is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through the string: '(' has 1 left bracket, '((' has 2, '(()' has 1, and so on. This means that after parsing the first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.

For example, if we have string '(***)', then as we parse each symbol, the set of possible values for the balance is [1] for '('; [0, 1, 2] for '(*'; [0, 1, 2, 3] for '(**'; [0, 1, 2, 3, 4] for '(***', and [0, 1, 2, 3] for '(***)'.

Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].

Algorithm

Let lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

If we encounter a left bracket (c == '('), then lo++, otherwise we could write a right bracket, so lo--. If we encounter what can be a left bracket (c != ')'), then hi++, otherwise we must write a right bracket, so hi--. If hi < 0, then the current prefix can't be made valid no matter what our choices are. Also, we can never have less than 0 open left brackets. At the end, we should check that we can have exactly 0 open left brackets.

Code (Java):

class Solution {
    public boolean checkValidString(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int lo = 0;
        int hi = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                lo++;
                hi++;
            } else if (c == ')') {
                if (lo > 0) {
                    lo--;
                }
                hi--;
            } else {
                if (lo > 0) {
                    lo--;
                }
                hi++;
            }

            if (hi < 0) {
                return false;
            }
        }

        return lo == 0;
    }
}

Leetcode 616. Add Bold Tag in String

Given a string s and a list of strings dict, you need to add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example 1:

Input: 
s = "abcxyz123"
dict = ["abc","123"]
Output:
"<b>abc</b>xyz<b>123</b>"

Example 2:

Input: 
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Output:
"<b>aaabbc</b>c"

Note:

1. The given dict won't contain duplicates, and its length won't exceed 100.
2. All the strings in input have length in range [1, 1000].

Code (Java):

class Solution {
    public String addBoldTag(String s, String[] dict) {
        if (dict == null || dict.length == 0) {
            return s;
        }

        // step 1: find start and end pos of the substring
        //
        List<Interval> intervals = new ArrayList<>();
        for (String t : dict) {
            strStr(s, t, intervals);
        }
        
        if (intervals.isEmpty()) {
            return s;
        }

        // step 2: sort the intervals based on the start index
        //
        Collections.sort(intervals, new IntervalComparator());

        // step 3: merge intervals
        //
        List<Interval> mergedIntervals = mergeIntervals(intervals);

        // step 4: compose the result based on the merged intervals
        //
        StringBuilder sb = new StringBuilder();
        int prev = 0;
        
        for (int i = 0; i < mergedIntervals.size(); i++) {
            Interval curr = mergedIntervals.get(i);
            // prev seg
            //
            sb.append(s.substring(prev, curr.start));
            sb.append("<b>");
            
            // curr seg
            //
            sb.append(s.substring(curr.start, curr.end + 1));
            sb.append("</b>");
            
            prev = curr.end + 1;
        }
        
        // trailing substring
        //
        if (prev < s.length()) {
            sb.append(s.substring(prev));
        }

        return sb.toString();
    }

    private void strStr(String s, String t, List<Interval> list) {
        for (int i = 0; i < s.length() - t.length() + 1; i++) {
            int j = 0;
            while (j < t.length()) {
                if (s.charAt(i + j) == t.charAt(j)) {
                    j++;
                } else {
                    break;
                }
            }

            if (j == t.length()) {
                Interval interval = new Interval(i, i + j - 1);
                list.add(interval);
            }
        }
    }

    private List<Interval> mergeIntervals(List<Interval> intervals) {
        List<Interval> ans = new ArrayList<>();
        
        if (intervals == null || intervals.isEmpty()) {
            return ans;
        }

        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev.end >= curr.start || prev.end + 1 == curr.start) {
                prev.end = Math.max(prev.end, curr.end);
            } else {
                ans.add(new Interval(prev.start, prev.end));
                prev = curr;
            }
        }

        ans.add(prev);

        return ans;
    }
}

class Interval {
        int start;
        int end;

        public Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval a, Interval b) {
        return a.start - b.start;
    }
}

Leetcode 680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Code (Java):

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }
        
        int left = 0;
        int right = s.length() - 1;
        
        while  ( left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        
        if (left >= right) {
            return true;
        }
            
        if (isPalin(s, left + 1, right) || 
            isPalin(s, left, right - 1)) {
                return true;
        }
        
        return false;
    }
    
    private boolean isPalin(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                break;
            }
        }
        
        return left >= right;
    }
}

Leetcode 606. Construct String from Binary Tree

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }

        String leftChild = tree2str(t.left);
        String rightChild = tree2str(t.right);

        if (leftChild.isEmpty() && rightChild.isEmpty()) {
            return t.val + "";
        }
        
        String r = (rightChild.isEmpty() ? "" : "(" + rightChild + ")");

        return t.val + "(" + leftChild + ")" + r;
    }
}

Leetcode 583. Delete Operation for Two Strings

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

1. The length of given words won't exceed 500.
2. Characters in given words can only be lower-case letters.

Code (Java):

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word2.length(); i++) {
            dp[0][i] = i;
        }

        for (int j = 1; j <= word1.length(); j++) {
            dp[j][0] = j;
        }

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}

Leetcode 557. Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Code (Java):

class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int start = 0;
        int end = 0;

        char[] arr = s.toCharArray();

        while (end < s.length()) {
            while (end < s.length() && s.charAt(end) != ' ') {
                end++;
            }
            reverse(arr, start, end - 1);
            end++;
            start = end;
        }

        reverse(arr, start, end - 1);

        return new String(arr);
    }

    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

Leetcode 556. Next Greater Element III

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer nand is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

Code (Java):

class Solution {
    public int nextGreaterElement(int n) {
        String s = n + "";
        char[] arr = s.toCharArray();

        // step 1: go from end and find the descreasing number
        //
        int i = s.length() - 2;
        while (i >= 0 && s.charAt(i) >= s.charAt(i + 1)) {
            i--;
        }

        if (i < 0) {
            return -1;
        }

        int j = i + 1;
        while (j < s.length() && s.charAt(j) > s.charAt(i)) {
            j++;
        }
        j--;

        swap(arr, i, j);

        reverse(arr, i + 1);

        String ans = new String(arr);
        
        Long l = Long.parseLong(ans);
        if (l >= Integer.MAX_VALUE) {
            return -1;
        }

        return Integer.parseInt(ans);
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }

    private void reverse(char[] arr, int start) {
        int end = arr.length - 1;

        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }
}

Leetcode 551. Student Attendance Record I

You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. 'A' : Absent.
2. 'L' : Late.
3. 'P' : Present.

A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

Code (Java):

class Solution {
    public boolean checkRecord(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }

        int cLate = 0;
        int cAbsent = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'A') {
                cAbsent++;
            } else if (c == 'L') {
                cLate = 0;
                // check the number of contiguous lates
                //
                while (i < s.length() && s.charAt(i) == 'L') {
                    cLate++;
                    i++;
                }
                i--;
            }

            if (cAbsent > 1 || cLate > 2) {
                return false;
            }
        }

        return true;
    }
}