LeetCode - String

Record the String topic algorithm problems.

0003. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

solution 1:

const lengthOfLongestSubstring = (s) => {
    const s_arr = s.split('');
    if (s_arr.length < 2) {
        return s_arr.length
    } else {
        let result = [s_arr[0]];
        let find = [s_arr[0]];
        for(let i = 1; i < s_arr.length; i++) {
            let index = find.indexOf(s_arr[i]);
            if (index === -1) {
                find.push(s_arr[i]);
            } else {
                if(find.length > result.length) {
                    result = find;
                }
                if(find.length > 1) {
                    find = find.slice(index + 1)
                    find.push(s_arr[i]);
                }
            }
        }
        return Math.max(result.length, find.length)
    }
};

Runtime: 84 ms
Memory Usage: 42.1 MB

solution 2:

const lengthOfLongestSubstring = s => {
    // keeps track of the most recent index of each letter.
    const map = {};
    // keeps track of the starting index of the current substring.
    var left = 0;

    return s.split('').reduce((max, v, i) => {
        // starting index of substring is 1 + (the last index of this letter) to ensure this letter is not counted twice.
        left = map[v] >= left ? map[v] + 1 : left;
        // updates last recorded index of letter to the most recent index.
        map[v] = i;

        // indices of current substring is (idx - leftIdx, idx).
        // +1 because if your substring starts and ends at index 0, it still has a length of 1.
        return Math.max(max, i - left + 1);
    }, 0)
};

Runtime: 100 ms
Memory Usage: 40.2 MB

0010. Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘‘.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or .
Example 1:
Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:
Input:
s = “aa”
p = “a“
Output: true
Explanation: ‘‘ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.
Example 3:
Input:
s = “ab”
p = “.“
Output: true
Explanation: “.*” means “zero or more () of any character (.)”.
Example 4:
Input:
s = “aab”
p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.
Example 5:
Input:
s = “mississippi”
p = “misisp.”
Output: false

solution1:

const isMatch = (s, p) => {
  const lenS = s.length;
  const lenP = p.length;
  const map = {};

  return check(0, 0);

  function check(idxS, idxP) {
    if (map[idxS + ':' + idxP] !== undefined) return map[idxS + ':' + idxP];
    if (idxS > lenS) return false;
    if (idxS === lenS && idxP === lenP) return true;

    if (p[idxP] === '.' || p[idxP] === s[idxS]) {
      map[idxS + ':' + idxP] = p[idxP + 1] === '*' ?
        check(idxS + 1, idxP) || check(idxS, idxP + 2) :
        check(idxS + 1, idxP + 1);
    } else {
      map[idxS + ':' + idxP] = p[idxP + 1] === '*' ?
        check(idxS, idxP + 2) : false;
    }
    return map[idxS + ':' + idxP];
  }
};

Runtime: 104 ms
Memory Usage: 42 MB

solution2:

const isMatch = (s, p) => {
    if (s.length === 0 && p.length === 0) {
        return true
    }
    
    if (s.length !== 0 && p.length === 0) {
        return false
    }
    
    if (s.length === 0 && p.length !== 0) {
        if (p[1] === '*') {
            return isMatch(s, p.slice(2))
        } else {
            return false
        }
    }
    
    if (p[1] === '*') {
        if (s[0] === p[0] || p[0] === '.') {
            return isMatch(s.slice(1), p) || isMatch(s, p.slice(2))    
        } else {
            return isMatch(s, p.slice(2))
        }
    } else {
        if (s[0] === p[0] || p[0] === '.') {
            return isMatch(s.slice(1), p.slice(1))
        } else {
            return false
        }
    }
};

Runtime: 168 ms
Memory Usage: 44.9 MB

0014. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: [“flower”,”flow”,”flight”]
Output: “fl”
Example 2:
Input: [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.

solution:

const longestCommonPrefix = (strs) => {
    if (!strs.length) {
        return '';
    }
    for (let i = 0; i < strs[0].length; i++) {
        for (let str of strs) {
          if (str[i] !== strs[0][i]) {
            return str.slice(0, i);
          }
        }
    }

    return strs[0];
};

Runtime: 64 ms
Memory Usage: 35.6 MB

0017. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

solution:

const letterCombinations = (digits) => {
const mappings = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
};

if (!digits || digits.length === 0) return [];
if (digits.length === 1) {
return mappings[digits];
}

let result = [];
let set1 = letterCombinations(digits.substr(0, 1));
let set2 = letterCombinations(digits.substr(1));

for (let i = 0; i < set1.length; i++) {
for (let j = 0; j < set2.length; j++) {
result.push(set1[i] + set2[j]);
}
}

return result;
};

Runtime: 48 ms
Memory Usage: 33.8 MB

0020. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: “()”
Output: true
Example 2:
Input: “()[]{}”
Output: true
Example 3:
Input: “(]”
Output: false
Example 4:
Input: “([)]”
Output: false
Example 5:
Input: “{[]}”
Output: true

solution:

const isValid = (s) => {
    const map = {
        "(": ")",
        "[": "]",
        "{": "}"
    }
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        const el = s[i];
        if (map[el]) {
            stack.push(map[el]);
        } else if (el !== stack.pop()) {
            return false;
        }
    }
    return stack.length === 0;
};

Runtime: 52 ms
Memory Usage: 33.9 MB

0022. Generate Parentheses

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:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

solution:

const generateParenthesis = (n) => {
const arr = [];
compose(n, n, '');
return arr;

    function compose(left, right, str) {
        if (!left && !right && str.length) {
            return arr.push(str);
        }
        if (left) {
            compose(left - 1, right, str + '(');
        }
        if (right > left) {
            compose(left, right - 1, str + ')');
        }
    }

};

Runtime: 56 ms
Memory Usage: 35.1 MB

0028. Implement strStr()

Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

solution:

const strStr = (haystack, needle) => {
  if (haystack === needle || needle === "") {
    return 0;
  }
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[0]) {
      let temp = haystack.substring(i, i + needle.length);
      if (temp === needle) {
        return i;
      }
    }
  }
  return -1;
};

Runtime: 60 ms
Memory Usage: 36.1 MB

0032. Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”
Example 2:
Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”

solution1:

const longestValidParentheses = (s) => {
    if (!s || !s.length) { return 0; }
    /* We will store the position of every invalid parenthesis.
       Once we have that, the solution is simply the longest
       subarray between two invalid parentheses */
    const invalids = new Set();
    /* We stack the opening parentheses as we find them,
       and pop them we we meet the corresponding closing
       parenthesis. Note that a closing ) always matches the
       latest opening ( one, hence the choice of a stack */
    const stack = [];

    for (let i=0; i<s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            // If we are closing an opening parenthesis, pop it out
            if (stack.length) {
                stack.pop();
            } else {
                /* Otherwise there is nothing to close,
                   hence this parenthesis is invalid */
                invalids.add(i);
            }
        }
    }

    /* Any remaining opening parenthesis that has not been closed is
       automatically invalid */
    while (stack.length) {
        invalids.add(stack.pop());
    }
    
    // Here we just count how many valid in between every invalid
    let max = 0, count = 0;
    for (let i=0; i<=s.length; i++) {
        if (i < s.length && !invalids.has(i)) {
            count++;
        } else {
            max = Math.max(max, count);
            count = 0;
        }
    }
    return max;
};

Runtime: 92 ms
Memory Usage: 42.2 MB

solution2:

const longestValidParentheses = (s) => {
  let dp = Array(s.length); // continous valid parentheses up to that ith point.
  let max = 0;
  dp[0] = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === ")") {
      if (s[i - 1] === "(") {
        dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
      } else if (
        i - 1 - dp[i - 1] >= 0 &&
        s[i - 1] === ")" &&
        s[i - 1 - dp[i - 1]] === "("
      ) {
        dp[i] =
          dp[i - 1] +
          (i - 1 - 1 - dp[i - 1] >= 0 ? dp[i - 1 - 1 - dp[i - 1]] : 0) +
          2;
      } else {
        dp[i] = 0;
      }
    } else {
      dp[i] = 0;
    }
    max = Math.max(max, dp[i]);
  }
  return max;
};

Runtime: 88 ms
Memory Usage: 42 MB

0038. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221
   1 is read off as “one 1” or 11.
   11 is read off as “two 1s” or 21.
   21 is read off as “one 2, then one 1” or 1211.
   Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
   Note: Each term of the sequence of integers will be represented as a string.
   Example 1:
   Input: 1
   Output: “1”
   Explanation: This is the base case.
   Example 2:
   Input: 4
   Output: “1211”
   Explanation: For n = 3 the term was “21” in which we have two groups “2” and “1”, “2” can be read as “12” which means frequency = 1 and value = 2, the same way “1” is read as “11”, so the answer is the concatenation of “12” and “11” which is “1211”.

solution:

const countAndSay = (n) => {
    let str = '1';
    for (let i = 1; i < n; i++) {
        let strArray = str.split('');
        str ='';
        let count = 1;
        // Loop through current nth level line
        for (let j = 0; j < strArray.length; j++) {
            // Next digit is different
            if (strArray[j] !== strArray[j+1]) {
                // Go to next non-matching digit
                str += count + strArray[j];
                count = 1;
            } else {
                count++;
            }
        }
    }
    return str;
};

Runtime: 72 ms
Memory Usage: 35.4 MB

0049. Group Anagrams

Given an array of strings, group anagrams together.
Example:
Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

solution:

const groupAnagrams = (strs) => {
  const map = {};
  for (let str of strs) {
    const key = [...str].sort().join('');
    if (!map[key]) {
      map[key] = [];
    }
    map[key].push(str);
  }
  return Object.values(map);
};

Runtime: 132 ms
Memory Usage: 46.9 MB

0076. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:
Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

solution:

const minWindow = (s, t) => {
    let ans = '';
    const map = {};
    t.split('').forEach(ch => map[ch] = (map[ch] || 0) + 1);
    let count = Object.keys(map).length;
    let l = 0;
    let r = -1;
    
    while (r < s.length) {
        if (count === 0) {
            if (!ans || r - l + 1 < ans.length) {
                ans = s.slice(l, r + 1);
            }
            if (map[s[l]] !== undefined) {
                map[s[l]]++;
            }
            if (map[s[l]] > 0) {
                count++;
            }
            l++;            
        } else {
            r++;
            if (map[s[r]] !== undefined) {
                map[s[r]]--;
            }
            if (map[s[r]] === 0) {
                count--;
            }
        }
    }
    return ans;
};

Runtime: 92 ms
Memory Usage: 41.2 MB

0125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: “A man, a plan, a canal: Panama”
Output: true
Example 2:
Input: “race a car”
Output: false

solution:

const isPalindrome = (s) => {
    const strippedString = s.replace(/\W/g, '');
    const reversedString = strippedString.split('').reverse().join('');
    return strippedString.toLowerCase() == reversedString.toLowerCase();
};

Runtime: 68 ms
Memory Usage: 38 MB

0344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.

Example 1:
Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2:
Input: [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

solution:

const reverseString = (s) => {
    let i = 0;
    var j = s.length - 1;
    while (i < j) {
        [s[i], s[j]] = [s[j], s[i]];
        i++;
        j--;
    }
};

Runtime: 124 ms
Memory Usage: 47.1 MB

0387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.
Examples:
s = “leetcode”
return 0.
s = “loveleetcode”,
return 2.
Note: You may assume the string contain only lowercase letters.

solution 1:

const firstUniqChar = (s) => {
    for(let i = 0; i < s.length; i++){
       if (s.indexOf(s[i]) === s.lastIndexOf(s[i])){
          return i;
      }
   }
   return -1;
};

Runtime: 84 ms
Memory Usage: 37.8 MB

solution 2:

const firstUniqChar = (s) => {
    let map = new Map();
    for(let i = 0; i < s.length; i++) {
         if(map.has(s[i])) {
             map.set(s[i],2);
         } else{
             map.set(s[i],1);
         }
     }

    for(let i = 0; i < s.length; i++) {
        if(map.has(s[i]) && map.get(s[i]) === 1) {
            return i;
        }
    }
    return -1;
};

Runtime: 100 ms
Memory Usage: 37.5 MB

0647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Note:
The input string length won’t exceed 1000.

solution:

const countSubstrings = (s) => {
    let count = 0;
    for(let i = 0; i < s.length; i++) {
        helper(s, i, i) //found all single number length Palindromic
        helper(s, i, i+1) //found all even number length Palindromic
    }
    return count;
    function helper(s, low, high) {
        while(low >= 0 && high <= s.length && s[low] === s[high]) {
            count++;
            low--;
            high++;
        }
    }
};

Runtime: 80 ms
Memory Usage: 35.6 MB