# 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](https://leetcode.com/problems/permutation-in-string/)

---

### [Same Tree](https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://leetcode.com/problems/word-ladder/)
---

## [Word Ladder 2](https://leetcode.com/problems/word-ladder-ii/)
---

## [Number of Islands](https://leetcode.com/problems/number-of-islands/)

---

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

)