Is Swap For Longest Repeated Character Substring easy or hard?

Swap For Longest Repeated Character Substring is classified as a Medium difficulty problem. The challenge comes from reasoning about how one swap can extend or merge character groups. Once you recognize the segmentation pattern or sliding window formulation, the implementation becomes straightforward.

Swap For Longest Repeated Character Substring Python/Java solution

Python and Java implementations typically start with counting character frequencies using an array of size 26. Then they iterate through the string to track repeating segments or maintain a sliding window that allows at most one mismatched character. Both implementations achieve O(n) time and O(1) extra space.

How to solve Swap For Longest Repeated Character Substring in O(n)?

First count the total occurrences of each character. Then scan the string and track contiguous segments or use a sliding window. If two segments of the same character are separated by one different character, combine their lengths and add one more if another identical character exists elsewhere. This keeps the algorithm linear while evaluating all possible swap improvements.

What is the best approach for Swap For Longest Repeated Character Substring?

The segmentation and swap strategy is the most intuitive and commonly recommended approach. It groups consecutive identical characters and checks whether two segments can merge by swapping a character from elsewhere. This method runs in O(n) time and O(1) space while clearly modeling how a single swap affects repeating substrings.

Is Swap For Longest Repeated Character Substring asked at Google/Amazon/Meta?

Problems involving longest repeating substrings and sliding window techniques appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test understanding of string segmentation, frequency counting, and window expansion logic. Mastering this problem strengthens pattern recognition for many substring optimization questions.

What data structure is used in Swap For Longest Repeated Character Substring?

The core data structures are a frequency array or hash table to count characters and optionally a list of segments representing contiguous character groups. Some implementations also use a sliding window with two pointers. These structures allow constant-time character frequency lookups during the scan.

What is the time complexity of Swap For Longest Repeated Character Substring?

The optimal solutions run in O(n) time where n is the length of the string. The algorithm performs a single pass to count character frequencies and another linear scan to analyze segments or sliding windows. Space complexity is O(1) because only fixed-size character frequency arrays are needed.

Description Hints 1 Solution Video 10:36

1156. Swap For Longest Repeated Character Substring

Medium44.9% acceptance2 companies

You are given a string text. You can swap two of the characters in the text.

Return the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.

Example 3:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.

Constraints:

1 <= text.length <= 2 * 10⁴
text consist of lowercase English characters only.

Asked at 2 companies

Nutanix

Google

Topics

Hints open one at a time

Hint 1

There are two cases: a block of characters, or two blocks of characters between one different character. By keeping a run-length encoded version of the string, we can easily check these cases.

10:36

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxRepOpt1(self, text: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"ababa"

Input

"aaabaaa"

Input

"aaaaa"

Your code is saved on this device.Solution