Find the longest identical substring after up to K replacements.

by Bhavik Bamania

JavaScript

// Problem: Longest Substring After K Replacements

// You are given a string s (uppercase letters) and an integer k.

//  You can replace at most k characters in the string.

// Return the length of the longest substring where all characters are the same after replacements.

// nput: s = "AABABBA", k = 1
// Output: 4
// s = "ABAB", k = 2
// Expected: 4
let s = "ABAB";
function findLongestSubStr(str, k) {
  let left = 0;
  let freq = new Map();
  let maxFreq = 0;
  let maxLen = 0;
  let returnStr = "";

  for (let right = 0; right < str.length; right++) {
    const char = str[right];
    freq.set(char, (freq.get(char) || 0) + 1);
    maxFreq = Math.max(maxFreq, freq.get(char));
    while ((right - left + 1) - maxFreq > k) {
      freq.set(str[left], freq.get(str[left]) - k);
      left++;
    }

    maxLen = Math.max(maxLen, right - left + 1)
    returnStr = str.slice(left, right + 1)
  }
  console.log(returnStr);
}

findLongestSubStr(s, 2);