(Longest Palindromic Substring)

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Thoughts:
The idea is to use a stack to store all the index of ‘(‘ we encountered. We maintain a variable “startIndex” to store the earliest starting position of a ‘(‘, this is used to determine the start position (hence the length) of a possible solution. If we see a ‘)’, we can pop out a ‘(‘ to construct a parenthesis. Hence we have a candidate. After doing that, if the stack is empty, we can fetch the earliest starting position to calculate the length of this solution (this scenario occurs when we see the last index of “(()())”). If the stack is not empty yet, we can calculate the length by comparing the current index with the index of the top element in the stack (this scenario happens when we process the last index of “(()”).
Code (Java):

import java.util.Stack;
public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int len = 0;
        int maxLen = 0;
        int startIndex = s.length();
        for(int i = 0; i < s.length(); ++i) {
            if(s.charAt(i) == '(') {
                stack.push(i);
                continue;
            }
            
            if(stack.isEmpty()) {
                startIndex = s.length();
            } else {
                startIndex = Math.min(stack.peek(), startIndex);
                stack.pop();
                
                if(stack.isEmpty()) {
                    len = i - startIndex + 1;
                } else {
                    len = i - stack.peek();
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}

Code (C++):

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> Stack;
        int len = 0;
        int maxLen = 0;
        int startIndex = s.size();
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == '(') {
                Stack.push(i);
                continue;
            }
            
            if(Stack.empty()) {
                startIndex = s.size();
            } else {
                startIndex = min(Stack.top(), startIndex);
                Stack.pop();
                
                if(Stack.empty()) {
                    len = i - startIndex + 1;
                } else {
                    len = i - Stack.top();
                }
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};

(Longest Substring Without Repeating Characters)

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 i. 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 0 \leq j \leq i-1, 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;
    }
};

(Longest Palindromic Substring)

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));
    }
};

Find the longest common prefix in an array of strings (Longest Common Prefix)

Write a function to find the longest common prefix string amongst an array of strings.

Thoughts:
Apparently this can be done in O(n). We start with the first string as the longest common prefix. We then go through every string in the array and compare the prefix with them. Update (shorten) the prefix if needed.

Code (Java):

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = new String();
        if(strs.length > 0)
            prefix = strs[0];
        for(int i = 1; i < strs.length; ++i) {
            String s = strs[i];
            int j = 0;
            for(; j < Math.min(prefix.length(), s.length()); ++j) {
                if(prefix.charAt(j) != s.charAt(j)) {
                    break;
                }
            }
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
}

Code (C++):

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        string prefix;
        if(strs.size() > 0)
            prefix = strs[0];
        for(int i = 1; i < strs.size(); ++i) {
            string s = strs[i];
            int j = 0;
            for(; j < min(prefix.size(), s.size()); ++j) {
                if(prefix[j] != s[j])
                    break;
            }
            prefix = prefix.substr(0, j);
        }
        return prefix;
    }
};

(Letter Combinations of a Phone Number)

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'] = " ";
    }
};

(Length of Last Word)

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = “Hello World”,
return 5.

Thoughts:
We just need to iterate from the last position of the string, find the first index that is not space, and count from there backwards.

Code (Java):

public class Solution {
    public int lengthOfLastWord(String s) {
        int length = 0;
        int i = s.length() - 1;
        while(i >= 0 && s.charAt(i) == ' ') {
            i--;
        }
        while(i >= 0 && s.charAt(i) != ' ') {
            length++;
            i--;
        }
        return length;
    }
}

Code (C++):

class Solution {
public:
    int lengthOfLastWord(const char *s) {
        int length = 0;
        int i = strlen(s) - 1;
        while(i >= 0 && s[i] == ' ') {
            i--;
        }
        while(i >= 0 && s[i] != ' ') {
            length++;
            i--;
        }
        return length;
    }
};

(Largest Rectangle in Histogram)

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

Thoughts:
The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan. We just need to compare: height[i] * (n – i) for every i. So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:

  1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of poped elements.
  2. Keep track of the maximum area that cause by those pop.

For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.

Code (Java):

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = 
            new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() || 
                height[i] >= stack.peek()) {
                stack.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack.isEmpty() && 
                    stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                    max = Math.max(max, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }
}

Code (C++):

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> stack_;
        int maxArea = 0;
        int i = 0;
        while(i < height.size()) {
            if(stack_.empty() || 
                height[i] >= stack_.top()) {
                stack_.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack_.empty() && 
                    stack_.top() > height[i]) {
                    count++;
                    int top = stack_.top();
                    stack_.pop();
                    maxArea = max(maxArea, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack_.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack_.empty()) {
            count++;
            maxArea = max(maxArea, stack_.top() * count);
            stack_.pop();
        }
        return maxArea;
    }
};

Previous Older Entries