Algorithm - LeetCode Problems 8

Problem 459. Repeated Substring Pattern

• Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Examples

• Example 1:

  • Input: s = "abab"
  • Output: true
  • Explanation: It is the substring "ab" twice.

• Example 2:

  • Input: s = "aba"
  • Output: false

Constraints:

• 1 <= s.length <= 10^4
• s consists of lowercase English letters.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    const totalLenth = s.length;
    for (let i = 1; i <= Math.floor(totalLenth/2); i++) {
        const str = s.substring(0, i);
        const repeatedStr = str.repeat(totalLenth/i)
        if (repeatedStr == s) {
            return true;
        }
    }
    return false;
};

Problem 1004. Max Consecutive Ones III

• Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Examples

• Example 1:

  • Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
  • Output: 6
  • Explanation: [1,1,1,0,0,1,1,1,1,1,1]
    • Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

• Example 2:

  • Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
    Output: 10
  • Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
    • Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function(nums, k) {
    let left = 0;
    let right = 0;
    
    while (right < nums.length) {
        if (nums[right] === 0) {
            k--;
        }
        if (k < 0) {
            if (nums[left] === 0) {
                k++;
            }
            left++;
        }
        right++;
    }

    return right - left;
};

Problem 3. Longest Substring Without Repeating Characters

• Given a string s, find the length of the longest substring without repeating characters.

Examples

• Example 1:

  • Input: s = "abcabcbb"
  • Output: 3
  • Explanation: The answer is "abc", with the length of 3.

• Example 2:

  • Input: s = "bbbbb"
  • Output: 1
  • Explanation: The answer is "b", with the length of 1.

Constraints

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const strSet = new Set();
    let maxLength = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const str = s[right];

        while (strSet.has(str)) {
            strSet.delete(s[left]);
            left++;
        }
        
        strSet.add(str);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};