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

__ATA.cmd.push(function() {
__ATA.initDynamicSlot({
location: 120,
formFactor: '001',
label: {
},
creative: {
},
privacySettings: {
text: 'Privacy',

}
}
});
});


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



(Jump Game II)

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Thoughts:
We use the similar approach as in Jump Game with the exception that table[i] now stores the minimum step it takes from position i to the last index. We update the table from end to start. At each position i, we look at every possible position j that one can reach from i, and then pick the least step it takes from j to the last index (i.e., table[j]). We then store table[j] + 1 in table[i]. When A[i] == 0, i.e., we cannot go anywhere from position i, we make table[i] = INT_MAX. Also when we cannot get to any intermediate position that will lead us to the last index, we make table[i] = INT_MAX.

Code (Java):

public class Solution {
public int jump(int[] A) {
int n = A.length;
int[] table = new int[n];
table[n-1] = 0;
for(int start = n - 2; start >= 0; --start) {
if(A[start] == 0) {
table[start] = Integer.MAX_VALUE;
} else if(n - 1 - start <= A[start]) {
table[start] = 1;
} else {
int min = Integer.MAX_VALUE;
for(int j = start + 1; j < n &&
j - start <= A[start]; ++j) {
if(table[j] < min) {
min = table[j];
}
}
table[start] = min == Integer.MAX_VALUE ?
min : min + 1;
}
}
return table[0];
}
}

Code (C++):
class Solution {
public:
int jump(int A[], int n) {
int *table = new int[n];
table[n-1] = 0;

for (int i = n-2; i >=0; i--) {
if (A[i] == 0)
table[i] = INT_MAX;
else if (A[i] >= n - i - 1)
table[i] = 1;
else {
int min = INT_MAX;
for (int j = i+1; j < n &&
j <= A[i] + i; j++) {
if (min > table[j])
min = table[j];
}
if (min != INT_MAX)
table[i] = min + 1;
else
table[i] = min;
}
}
return table[0];
}
};



(Jump Game)

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Thoughts:
This is definitely do-able through recursion. I actually tried but got time exceed limit. So I came up with this iterative method with $O(n^2)$ time complexity. We maintain a boolean table where table[i] stores whether you can reach the last index starting from index i. We start populating the table from the last position (n-1) of the array. We are at destination here so table[n-1] is always true. For each i, we look at all table values from i + 1 to n – 1. If we found a true value at j, we know we can reach the last index from j, so we just need to examine if we can reach index j from index i. If we can, then table[i] will be true and we don’t need to see the rest. In the worst case, for each i, we need to check every element from i + 1 to n – 1 so this is $O(n^2)$.

Code (C++):

class Solution {
public:
bool canJump(int A[], int n) {
bool *table = new bool[n];
table[n-1] = true;
int start = n - 2;
while(start >= 0) {
table[start] = false;
for(int j = start + 1; j < n; ++j) {
if(table[j] && j - start <= A[start]) {
table[start] = true;
break;
}
}
start--;
}
return table[0];
}
};

Code (Java):
public class Solution {
public boolean canJump(int[] A) {
boolean[] table = new boolean[A.length];
table[A.length-1] = true;
int start = A.length - 2;
while(start >= 0) {
table[start] = false;
for(int j = start + 1; j < A.length; ++j) {
if(table[j] && j - start <= A[start]) {
table[start] = true;
break;
}
}
start--;
}
return table[0];
}
}



Convert an integer to a roman numeral (Integer to Roman)

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Thoughts:
Not a hard problem. Only tricky point is that 4 is “IV” not “IIII”, 9 is “IX” not “VIIII” or “VIV”. First, we might think the bases are { 1000, 500, 100, 50, 10, 5, 1}, but if we use bases { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }, this problem would become really easy.

Code (C++):

class Solution {
public:
string intToRoman(int num) {
setup();
string s;
for(map<int, string>::reverse_iterator it = romanMap.rbegin();
it != romanMap.rend(); ++it) {
while(num >= it -> first) {
s += it -> second;
num -= it -> first;
}
}
return s;
}

private:
map<int, string> romanMap;

void setup() {
romanMap[1000] = "M";
romanMap[900] = "CM";
romanMap[500] = "D";
romanMap[400] = "CD";
romanMap[100] = "C";
romanMap[90] = "XC";
romanMap[50] = "L";
romanMap[40] = "XL";
romanMap[10] = "X";
romanMap[9] = "IX";
romanMap[5] = "V";
romanMap[4] = "IV";
romanMap[1] = "I";
}
};

Code (Java):
public class Solution {
private static int[] bases = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9,
5, 4, 1 };
private static HashMap<Integer, String> map = new HashMap<Integer, String>();

private static void setup() {
map.put(1, "I");
map.put(4, "IV");
map.put(5, "V");
map.put(9, "IX");
map.put(10, "X");
map.put(40, "XL");
map.put(50, "L");
map.put(90, "XC");
map.put(100, "C");
map.put(400, "CD");
map.put(500, "D");
map.put(900, "CM");
map.put(1000, "M");
}

public String intToRoman(int num) {
setup();
String result = new String();
for (int i : bases) {
while (num >= i) {
result += map.get(i);
num -= i;
}
}
return result;
}
}