Categories
Uncategorized

438. Find All Anagrams in a String Leetcode Javascript Solution

The Problem:

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

The Solution:

var findAnagrams = function(s, p) {
    let set = new Map()
    for(let i = 0; i < p.length; i++){
        if(!set.has(p[i])){
            set.set(p[i],1)
        } else{
            set.set(p[i],set.get(p[i]) + 1)
        }
    }
   // console.log(set)
    let ans = []
     let left = 0, right = 0, count = set.size
     while (right < s.length){
         if(set.has(s[right])){
             set.set(s[right],set.get(s[right]) - 1)
             if(set.get(s[right])== 0){
                 count--
             }
         }
         while(count == 0){
             if(set.has(s[left])){
                    set.set(s[left],set.get(s[left]) + 1)
                 if(set.get(s[left]) > 0){
                 count++
             }
             }
             if(right - left +1 == p.length){
                 ans.push(left)
             }
             left++
         }
         right++
     }
    return ans
};
Categories
Uncategorized

32. Longest Valid Parentheses Leetcode Javascript Solution

The Problem:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

The Solution:

var longestValidParentheses = function(s) {
   let max = 0, count = 0
   for(let i = 0; i < s.length; i++){
         count = 0
       for(let j = i; j < s.length; j++){
           if(s[j] == "("){
               count++
           } else {
               count--
           }
           if(count < 0){
               break
           }
           if(count == 0){
              // console.log(" i " + i + " j " + j)
               max = Math.max(max,j-i + 1)
           }
       }
   }
    return max
};
Categories
Uncategorized

5. Longest Palindromic Substring Leetcode Javascript Solution

The Problem:

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

The Solution:

var longestPalindrome = function(s) {
    let n = s.length, left = 0, right = 0, maxLen = -56
    for(let i = 0 ; i < n; i++){
        let len1 = expand(i,i,s)
        let len2 = expand(i,i+1,s)
       // console.log( "len1 " + len1 + " len2 " + len2)
        let len =Math.max(len1,len2)
        if(maxLen < len){
            maxLen = len
            //case when the palindrome has an even no of characters
            if(maxLen % 2 == 0){
              //we need to add 1 to i to account for the fact that even-palindrome has 2 characters at the middle, we need to add 1 to i to make it similar to the case when the palindrome has an odd no of characters. This way, when we divide maxLen by 2, we get correct distance of the start of the string from the middle
            left = i +1 - Math.floor(maxLen/2)
            right = i + Math.floor(maxLen/2) + 1
            } else {
                 left = i - Math.floor(maxLen/2)
            right = i + Math.floor(maxLen/2) + 1
            }
        }
    }
    //console.log(maxLen + " left " + left)
    return s.substr(left,right - left )
    function expand(left,right,s){
        if(s.length == 0){
            return 0
        }
        while(left >=0 && right < s.length && s[left] == s[right]){
            left--
            right++
        }
        return right - left -1
    }
};
Categories
Uncategorized

214. Shortest Palindrome Leetcode Javascript Solution

The Problem:

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of lowercase English letters only.

The Solution:

We create a reverse string rev of string s. We know that the part of string s from 0,n-i that is equal to the part of string rev from i to the end is a palindrome. We then just need to append the remaining part of string rev and append it to string s to arrive at the answer.

var shortestPalindrome = function(s) {
    let rev = s.split('').reverse().join('')
    //console.log(rev)
    let n = s.length
    for(let i = 0 ; i < n; i++){
        if(s.substr(0,n-i) == rev.substr(i)){
            return rev.substr(0,i) + s
        }
    }
    return ''
};
Categories
Uncategorized

1771. Maximize Palindrome Length From Subsequences Leetcode Javascript Solution

The problem:

You are given two strings, word1 and word2. You want to construct a string in the following manner:

  • Choose some non-empty subsequence subsequence1 from word1.
  • Choose some non-empty subsequence subsequence2 from word2.
  • Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

palindrome is a string that reads the same forward as well as backward.

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

Constraints:

  • 1 <= word1.length, word2.length <= 1000
  • word1 and word2 consist of lowercase English letters.

The solution:

Dynamic Programming Approach: (100% time and space)

var longestPalindrome = function(word1, word2) {
    let s = word1 + word2
    let ans = 0
   // console.log(s)
    let dp = new Array(s.length).fill(0).map(el => new Array(s.length).fill(0));
    for(let i = 0 ; i < s.length; i++){
        dp[i][i] = 1
    }
    for(let l = 2; l <= s.length; l++){
        for(let i = 0; i < s.length - l +1; i++){
            let j = i+l-1
            if(l==2){
                if(s[i]== s[j]){
                    dp[i][j] = 2
                     if(i < word1.length && j >= word1.length){
                        ans = Math.max(ans, dp[i][j])
                    }
                } else {
                    dp[i][j] = 1
                }
            } else {
                if(s[i]== s[j]){
                    dp[i][j] = dp[i+1][j-1] + 2
                    if(i < word1.length && j >= word1.length){
                        ans = Math.max(ans, dp[i][j])
                    }
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
                }
            }
        }
    }
    return ans
};