6. ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    var data = new Array(numRows);
    var up = false; // up or down? used in-between tops and bottoms
    
    for(var i = 0, j = 0; i < s.length; i ++){
        // init arr elems
        if(data[j] === undefined){
            data[j] = "";
        }
        // append cur char
        data[j] += s.charAt(i);
        
        
        if(j == 0){
            // On top
            up = false; // Change direction
            j ++;
        } else if(j == numRows-1){
            // On bottom
            up = true;  // Then go up
            j --;
        } // in-between, follow prev direction
        else if(up){
            j --;
        } else {
            j ++;
        }
    }
    // Join/concat arr of str to single arr 
    return data.join("");
};

5. 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.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {\
    // palindromic str for single round
    var o = ""; 
    // Longest palindromic str
    var max = "";
    for (var i = 0; i < s.length; i ++){
        var x = i;
        var y = i;
        // Include current char
            o = s[i];
            
            // Collect Same letters on the right
        while(s[y+1] == s[y]){
            y ++; i ++;
            // append same char on the right to p_str
            o += s[i];
        } 
        
        // Then check both sides one by one
        // Make sure x & y in range, then compare both ends
        while(x > 0 
                && y < s.length-1 
                && s[x-1] == s[y+1]){
            o = s[x-1] + o + s[y+1];
            // Separate x & y for one more step
            x--; y++;
        }
        
        // Save, if longer than current max record
        if(o.length > max.length){
            max = o;
        }
        
    }
    
    return max;
};

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // remove elements from both ends

    
    while ((nums1.length + nums2.length)/2 > 1){
        // If any of the arrays is empty, rm the other one
        if(nums1.length == 0){
            nums2.shift();
            nums2.pop();
        } else if(nums2.length == 0){
            nums1.shift();
            nums1.pop();
        } else {
            if(nums1[0] < nums2[0]){
                nums1.shift();
            } else {
                nums2.shift();
            }
            // if nums1 is empty 
            //   OR nums1's tail is less than nums2's, remove nums2
            if(nums1.length == 0 || 
               nums1[nums1.length -1] < nums2[nums2.length -1]){
                nums2.pop();
            } else {
                nums1.pop();
            }
        }
    }
    // only 1 or 2 elements remain now
    var r = nums1.concat(nums2);
    // send average for two
    if(r.length > 1){
        return (r[0]+r[1])/2;
    } else {
    // or just the last element
        return r[0];
    }
};

3. Longest Substring Without Repeating

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.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var max = 0;
    var a = [];
    for (var i = 0; i < s.length; i ++){
        // If element exists, remove any other elements before it, 
        // and itself
        if(a.includes(s[i])){
            a.splice(0, a.indexOf(s[i]) + 1);
        }
        // Append new element
        a.push(s[i]);
        // Update result
        if(max < a.length){
            max = a.length;
        }
    }
    return max;
};