Runhe Tian Coding Practice

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Thoughts:
We want to finish this task in one scan. We can maintain a hashtable to detect if we have seen any character. We start from the beginning and walk through the array until we hit a repetition, let’s say, at position . We then have two piece of valuable information right now:

1. s[0..i-1] is a candidate of the longest substring without repetition. Therefore we can update the max length.
2. There exists a position , such that s[j] == s[i]. Substring starting from j is not a candidate because it has at least one repetition: s[j] and s[i]. Any substring ended at j will be shorter than the substring s[0..i-1] so we don’t need to look at them.

Then we can remove every elements in the hashtable from 0 to j, and make the start position of next candidate to j + 1. We keep walking and repeating this process until we hit the last element.

Code (Java):

import java.util.HashSet;
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        int candidateStartIndex = 0;
        for(int iter = 0; iter < s.length(); ++iter) {
            char c = s.charAt(iter);
            if(set.contains(c)) {
                max = Math.max(max, iter - candidateStartIndex);
                while(s.charAt(candidateStartIndex) 
                        != s.charAt(iter)) {
                    set.remove(s.charAt(candidateStartIndex));
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                set.add(c);
            }
        }
        max = Math.max(max, s.length() - candidateStartIndex);
        return max;
    }
}

Code (C++):
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unsigned int maxLen = 0;
        set<char> hashtable;
        int candidateStartIndex = 0;
        for(unsigned int iter = 0; iter < s.size(); ++iter) {
            char c = s[iter];
            if(hashtable.find(c) != hashtable.end()) {
                maxLen = max(maxLen, iter - candidateStartIndex);
                while(s[candidateStartIndex] != s[iter]) {
                    hashtable.erase(s[candidateStartIndex]);
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                hashtable.insert(c);
            }
        }
        maxLen = max(maxLen, s.size() - candidateStartIndex);
        return maxLen;
    }
};

	

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.

Thoughts:
Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.

Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        for(int len = s.length(); len > 0; --len) {
            for(int j = 0; j <= s.length() - len; ++j) {
                String sub = s.substring(j, j + len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return new String();
    }
    
    private boolean isPalindrome(String s) {
        if(s.length() <= 1)
            return true;
        else
            return s.charAt(0) == s.charAt(s.length()-1) && 
                isPalindrome(s.substring(1,s.length()-1));
    }
}

Code (C++):
class Solution {
public:
    string longestPalindrome(string s) {
        for(int len = s.size(); len > 0; --len) {
            for(int i = 0; i <= s.size() - len; ++i) {
                string sub = s.substr(i, len);
                if(isPalindrome(sub))
                    return sub;
            }
        }
        return "";
    }
    
private:
    bool isPalindrome(string s) {
        if(s.size() <= 1)
            return true;
        else
            return s[0] == s[s.size() - 1] && 
            isPalindrome(s.substr(1,s.size()-2));
    }
};

	

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

public class Solution {
    private HashMap<Character, String> map;
    
    public ArrayList<String> letterCombinations(String digits) {
        setup();
        ArrayList<String> solutions
            = new ArrayList<String>();
        recursion(digits, 0, new String(), solutions);
        return solutions;
    }
    
    private void recursion(String digits, int start, 
        String sol, ArrayList<String> solutions) {
        if(sol.length() > digits.length()) {
            return;  
        } else if(sol.length() == digits.length()) {
            solutions.add(sol);
            return;
        } else {
            for(int i = start; i < digits.length(); ++i) {
                String letters = map.get(digits.charAt(i));
                for(int j = 0; j < letters.length(); ++j) {
                    recursion(digits, i + 1, sol + letters.charAt(j), solutions);
                }
            }
        }
    }
    
    private void setup() {
        map = new HashMap<Character, String>();
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        map.put('0', " ");
    }
}

Code (C++):
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        setup();
        vector<string> solutions;
        string s;
        recursion(digits, 0, s, solutions);
        return solutions;
    }
    
private:
    map<char, string> mapping;
    void recursion(string digits, int start, 
        string sol, vector<string>& solutions) {
        if(sol.size() > digits.size()) {
            return;  
        } else if(sol.size() == digits.size()) {
            solutions.push_back(sol);
            return;
        } else {
            for(int i = start; i < digits.size(); ++i) {
                string letters = mapping[digits[i]];
                for(int j = 0; j < letters.size(); ++j) {
                    recursion(digits, i + 1, sol + letters[j], solutions);
                }
            }
        }
    }
    
    void setup() {
        mapping.clear();
        mapping['1'] = "";
        mapping['2'] = "abc";
        mapping['3'] = "def";
        mapping['4'] = "ghi";
        mapping['5'] = "jkl";
        mapping['6'] = "mno";
        mapping['7'] = "pqrs";
        mapping['8'] = "tuv";
        mapping['9'] = "wxyz";
        mapping['0'] = " ";
    }
};

	

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Thoughts:
Recursion. Base case is which the solution has size of . Recursive step: each time we count number of open parenthesis and closed parenthesis. If open == closed, then we have to add open parenthesis. If open > closed, we can add open parenthesis as long as we do not exceed . We can also add closed parenthesis.

Code (Java):

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> solutions = new ArrayList<String>();
        recursion(n, new String(), solutions);
        return solutions;
    }

    private void recursion(int n, String str, ArrayList<String> sol) {
        if(str.length() == 2 * n)
            sol.add(str);
        else {
            int left = 0;
            int right = 0;
            for(int i = 0; i < str.length(); ++i) {
                if(str.charAt(i) == '(')
                    left++;
                if(str.charAt(i) == ')')
                    right++;
            }
            if(left == right)
                recursion(n, str + "(", sol);
            else if(right < left) {
                if(left < n)
                    recursion(n, str + "(", sol);
                recursion(n, str + ")", sol);
            }
        }
    }
}

Code (C++):
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> solutions;
        string solution;
        recursion(n, solution, solutions);
        return solutions;
    }

    void recursion(int n, string solution, vector<string> &solutions) {
        if(solution.size() == 2*n) {
            solutions.push_back(solution);
        } else {
            int left = 0;
            int right = 0;
            for(int i = 0; i < solution.size(); ++i) {
                if(solution[i] == '(')
                    left++;
                if(solution[i] == ')')
                    right++;
            }
            if(left == right)
                recursion(n, solution + "(", solutions);
            else if(left > right) {
                if(left < n)
                    recursion(n, solution + "(", solutions);
                recursion(n, solution + ")", solutions);
            }
        }
    }
};

	

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12” is 2.

Thoughts:
Again, we can use recursion with backtracking. Each time we try to encode the first digit in the message to a letter, or we can encode the first two digits into a letter if possible, we then recursively do the samething for the sub-string. When there is no way to encode (e.g., encountering a single ‘0’, or encountering ’32’ and tyring to encode the two-digits to a letter), we simply return. If there is no sub-string to go on, we know we have found a valid solution, so we increase the count.

Code (C++):

class Solution {
public:
    int numDecodings(string s) {
        int solutions = 0;
        if(s.size() != 0)
            recursion(s, solutions);
        return solutions;
    }
    
    void recursion(string s,int &solutions) {
        if(s.size() == 0){
            solutions++;
        } else {
            int value = (int)s.at(0)- '0';
            if(value > 0 && value <= 9) {
                recursion(s.substr(1), solutions);
            }
            
            if(s.size() >= 2) {
                int value1 = (int)s.at(0) - '0';
                int value2 = (int)s.at(1) - '0';
                if(value1 == 1 && value2 >= 0 && value2 <= 9) {
                    recursion(s.substr(2), solutions);
                } else if(value1 == 2 && value2 >= 0 && value2 <= 6) {
                    recursion(s.substr(2), solutions); 
                }
            }
        }
    }
};

Code (Java):

This is a very werid way to do it, I know. The ArrayList solutions are pretty much useless there other than counting the number of valid solutions. It’s just a way to bypass the fact that Java cannot pass argument by reference.
import java.util.ArrayList;
public class Solution {
    public int numDecodings(String s) {
        ArrayList<Integer> solutions = new ArrayList<Integer>();
        if(s.length() != 0)
            recursion(s, solutions);
        return solutions.size();
    }
    
    private void recursion(String s, ArrayList<Integer> solutions) {
        if(s.length() == 0){
            solutions.add(1);
        } else {
            int value = Character.getNumericValue(s.charAt(0));
            if(value > 0 && value <= 9) {
                recursion(s.substring(1), solutions);
            }
            
            if(s.length() >= 2) {
                int value1 = Character.getNumericValue(s.charAt(0));
                int value2 = Character.getNumericValue(s.charAt(1));
                if(value1 == 1 && value2 >= 0 && value2 <= 9) {
                    recursion(s.substring(2), solutions);
                } else if(value1 == 2 && value2 >= 0 && value2 <= 6) {
                    recursion(s.substring(2), solutions); 
                }
            }
        }
    }
}