Find Longest Special Substring That Occurs Thrice I - Video Solutions

Problem Overview: You are given a string and need the length of the longest special substring that appears at least three times. A special substring contains only one repeating character (for example "aaa" or "bbbb"). Overlapping occurrences count, so the same region of the string can contribute to multiple substrings.

Approach 1: Sliding Window and Frequency Map (O(n) time, O(n) space)

Scan the string and group consecutive identical characters into runs such as a^3, b^2, a^4. For a run of length L, every substring length from 1..L is a valid special substring. Maintain a frequency structure for each character that counts how many times a substring of a certain length appears. While iterating through runs, update counts and track when a substring length reaches frequency ≥ 3. The key insight: special substrings are completely determined by consecutive runs, so you never need to enumerate arbitrary substrings. This approach relies on linear scans and constant-time updates using a hash table or array per character. Since each character is processed once and each run contributes limited updates, the overall complexity stays O(n) time with O(n) auxiliary space.

Approach 2: Dynamic Programming by Run Lengths (O(n^2) time, O(n) space)

Define a DP state where dp[i] stores the length of the consecutive identical-character substring ending at index i. If s[i] == s[i-1], extend the run; otherwise reset to 1. Once these run lengths are known, iterate through possible substring sizes and count how many times each length appears for the same character. When the count for a length reaches three, update the answer. This method is straightforward and easy to reason about, but checking many substring lengths leads to O(n^2) time in the worst case. It still uses only O(n) memory for the DP array. The idea combines concepts from string processing and frequency counting.

Recommended for interviews: The sliding window and run-length counting approach is the expected solution. It demonstrates that you recognize the structure of special substrings and avoid brute-force enumeration. Interviewers usually look for the observation that identical-character runs generate all valid substrings, which turns the problem into a counting task rather than substring generation. Techniques related to sliding window or binary search on substring length are common follow-ups if the problem is extended.