Competitive Coding

Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

/**
 * @param {string} s
 * @return {number}
 * 
 * Time Complexity: O(N)
 * Space Cmplexity: O(1) i.e constant
 */
var lengthOfLongestSubstring = function(s) {
    
    let startIndex=0;
    let ans=0;
    const visitedMap=new Map();
    
    for(let i=0;i<s.length;i++){
        const lastIndex= visitedMap.get(s[i]);
        if(lastIndex===undefined || lastIndex<startIndex){
            ans=Math.max(ans,i-startIndex+1);
        }
        else{
            startIndex=lastIndex+1;
        }
        visitedMap.set(s[i],i);
    }

    return ans;
};

---

Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1 Output: ["()"]

Approach:

If the generate all the possible permutations,time complexity will be O(2^n).

What if we generate only those permutations which we know for sure will be valid? It should reduce the time considerably. We can use backtracking for this purpose.

• Number of opening parentheses should be less than n.
• A closing parenthesis cannot occur before the open parenthesis.

/**
 * @param {number} n
 * @return {string[]}
 * Time Complexity: way less than O(2^N)
 */
var generateParenthesis = function(n) {
     const result = [];
    
    function R(str, open, close) {
    // Base condition
        if (open === n && close === n) {
            result.push(str);
            return;
        }
        // If the number of _open parentheses is less than the given n
        if (open < n) {
            R(str + "(", open + 1, close);
        }
        // If we need more close parentheses to balance
        if (close < open) {
            R(str + ")", open, close + 1);
        }
    };
    
    
    // Recursively generate parentheses
    R("", 0, 0);
    
    return result;
};

---

Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

---

Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

---

Container With Most Water

https://leetcode.com/problems/container-with-most-water/

---

Two Sum

https://leetcode.com/problems/two-sum/

---

Three Sum

https://leetcode.com/problems/3sum/

---

Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

---

Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

---

Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

---

Permutation in String

---

Same Tree

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    
    if(!p && !q){
        return true;
    }
    
    if(!p || !q){
        return false;
    }
    
    if(p.val !=q.val){
        return false;
    }
    
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
};

---

Symmetric Tree

function R(node1,node2){
    
    if(!node1 && !node2){
        return true;
    }
    
    if(!node1 || !node2){
        return false;
    }
    
    if(node1.val!=node2.val){
        return false;
    }
    
    return R(node1.left,node2.right) && R(node1.right,node2.left);
    
}


/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    
    return R(root.left,root.right);
};

---

Word Ladder

---

Word Ladder 2

---

Number of Islands

---

[Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/

)