Longest Substring with Repeating Letters after Replacement

Problem Statement

Given a string with lowercase letters only, if you are allowed to replace no more than ‘k’ letters with any letter, find the length of the longest substring having the same letters after replacement.

Example 1:

Input: String="aabccbb", k=2
Output: 5
Explanation: Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb".

Example 2:

Input: String="abbcb", k=1
Output: 4
Explanation: Replace the 'c' with 'b' to have a longest repeating substring "bbbb".

Example 3:

Input: String="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to have the longest repeating substring "ccc".
function length_of_longest_substring(str, k) {let windowStart = 0,maxLength = 0,maxRepeatLetterCount = 0,frequencyMap = {};// Try to extend the range [windowStart, windowEnd]for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {const rightChar = str[windowEnd];if (!(rightChar in frequencyMap)) {frequencyMap[rightChar] = 0;}frequencyMap[rightChar] += 1;maxRepeatLetterCount = Math.max(maxRepeatLetterCount, frequencyMap[rightChar]);// Current window size is from windowStart to windowEnd, overall we have a letter which is// repeating 'maxRepeatLetterCount' times, this means we can have a window which has one letter// repeating 'maxRepeatLetterCount' times and the remaining letters we should replace.// if the remaining letters are more than 'k', it is the time to shrink the window as we// are not allowed to replace more than 'k' lettersif ((windowEnd - windowStart + 1 - maxRepeatLetterCount) > k) {leftChar = str[windowStart];frequencyMap[leftChar] -= 1;windowStart += 1;}maxLength = Math.max(maxLength, windowEnd - windowStart + 1);}return maxLength;}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Arrays in JavaScript

Create a WhatsApp Clone with Next.js: Fetch Data from Firebase

NextJs Firebase v9 Part 10: Link to detail page

How to Turn React Component into Native Web Component

Okhttp3 Authenticator — 401 Unauthorized

Demystifying React Hooks

React about React-Context-API

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
SunJet Liu

SunJet Liu

More from Medium

Certified in Copado — Is it worth it?

Morrslieb is Made of Cheese

opploans/myoffer promo code

ITALO REBRANDS TO SYFER!