Longest Repeated Character Replacement

Data Structures and Algorithms

Statement

Given a string s and integer k, find the length of the longest substring of s, such that all characters of that substring are identical after replacing at most k characters with any other character.

Constraints

• -1 ≤ s.length() ≤ 10³
• 0 ≤ k ≤ s.length()
• s consists of only lowercase English characters

Solution

"""
production algorithm
"""

from collections import defaultdict


class Solution:
    def longest_repeated_character_replacement(self, string, capacity):
        """
        time complexity O(n)
        space complexity O(1)
        """
        length, low, high = len(string), 0, 0
        max_frequency, frequencies = -1, defaultdict(int)

        for high in range(length):
            frequencies[string[high]] = frequencies[string[high]] + 1
            max_frequency = max(max_frequency, frequencies[string[high]])
            if capacity < high - low + 1 - max_frequency:
                frequencies[string[low]] = frequencies[string[low]] - 1
                low = low + 1

        return high - low + 1

"""
unit tests
"""

from unittest import TestCase
from algorithms.sliding_window.longest_repeated_character_replacement.solution import Solution


class SolutionTestCase(TestCase):
    def test_longest_repeated_contiguous_at_start(self):
        # Given
        string = "aaaaaaaaaaxerkjysuhf"
        capacity = 2
        solution = Solution()

        # When
        actual = solution.longest_repeated_character_replacement(
            string, capacity)

        # Then
        expected = 12
        self.assertEqual(actual, expected)

    def test_longest_repeated_contiguous_at_middle(self):
        # Given
        string = "wzomqaaaaaaaaaaysuhf"
        capacity = 2
        solution = Solution()

        # When
        actual = solution.longest_repeated_character_replacement(
            string, capacity)

        # Then
        expected = 12
        self.assertEqual(actual, expected)

    def test_longest_repeated_contiguous_at_end(self):
        # Given
        string = "wzomqvtnlbaaaaaaaaaa"
        capacity = 2
        solution = Solution()

        # When
        actual = solution.longest_repeated_character_replacement(
            string, capacity)

        # Then
        expected = 12
        self.assertEqual(actual, expected)

    def test_longest_repeated_noncontiguous_at_start(self):
        # Given
        string = "aaaaavaaaaaerkjysuhf"
        capacity = 2
        solution = Solution()

        # When
        actual = solution.longest_repeated_character_replacement(
            string, capacity)

        # Then
        expected = 12
        self.assertEqual(actual, expected)

    def test_longest_repeated_noncontiguous_at_middle(self):
        # Given
        string = "wzoaaaaalbaaaaaysuhf"
        capacity = 2
        solution = Solution()

        # When
        actual = solution.longest_repeated_character_replacement(
            string, capacity)

        # Then
        expected = 12
        self.assertEqual(actual, expected)

    def test_longest_repeated_noncontiguous_at_end(self):
        # Given
        string = "wzomqvtnlaaaaajaaaaa"
        capacity = 2
        solution = Solution()

        # When
        actual = solution.longest_repeated_character_replacement(
            string, capacity)

        # Then
        expected = 12
        self.assertEqual(actual, expected)

Strategy

Sliding Window.

Explanation

At each step of the high index, add the character of the high index to the window and so increment its frequency in the window. If the window has more characters than can be replaced such that all characters in the window are identical, then remove the character of the low index from the window and so decrement its frequency in the window. The algorithm slides a window over all characters of the string, the window widens to the maximum length such that all characters in the window can be identical after replacement, and it never shrinks.

Time Complexity

The time complexity of the algorithm is O(n).

Space Complexity

The auxiliary space complexity of the algorithm is O(1) since at most 26 characters are kept in the frequencies store.

Links

data_structures_algorithms/algorithms/sliding_window/longest_repeated_character_replacement at main…