LeetCode: Longest Repeating Character Replacement

Posted on January 25, 2018July 26, 2020 by braindenny

Longest Repeating Character Replacement

Similar Problems:

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:

Both the string’s length and k will not exceed 10^4.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: without helper function

// https://code.dennyzhang.com/longest-repeating-character-replacement
// Basic Ideas: sliding timewindow
//
//  Notice: 
//    How to check whether a string can be changed to repeating characters by k operations/
//    The time complexity is O(1)!
//
// Corner cases:
//   "BAAAB", 2
//   "BAAA", 2
//
// Complexity: Time O(n), Space O(1)
func characterReplacement(s string, k int) int {
    l := make([]int, 26)
    res := 0
    // s[i...j]
    i:=0
    uniqCnt := 0
    for j, ch := range s {
        // move right
        index:=byte(ch)-'A'
        l[index]++
        if l[index] > uniqCnt {
            uniqCnt = l[index]
        }
        // move left
        for j-i+1-uniqCnt>k {
            l[s[i]-'A']--
            i++
        }
        // collect result
        if j-i+1>res {
            res = j-i+1
        }
    }
    return res
}

Solution: with helper function

// https://code.dennyzhang.com/longest-repeating-character-replacement
// Basic Ideas: sliding timewindow
//
//  Notice: 
//    How to check whether a string can be changed to repeating characters by k operations/
//    The time complexity is O(1)!
//
// Corner cases:
//   "BAAAB", 2
//   "BAAA", 2
//
// Complexity: Time O(n), Space O(1)
func isRepeatingAtMostK(l []int, k int) bool {
    sum, max := 0, 0
    for _, v := range l {
        sum += v
        if v > max {
            max = v
        }
    }
    return sum-max <= k
}

func characterReplacement(s string, k int) int {
    l := make([]int, 26)
    res := 0
    // s[i...j]
    i:=0
    for j, ch := range s {
        // move right
        l[byte(ch)-'A']++
        // move left
        for !isRepeatingAtMostK(l, k) {
            l[s[i]-'A']--
            i++
        }
        // collect result
        if j-i+1>res {
            res = j-i+1
        }
    }
    return res
}

Post Views: 7