Skip to main content
Talentd

Find Longest Special Substring That Occurs Thrice I - Solution & Explanation

MediumHash TableStringBinary SearchSliding Window22 min readAsked at: Microsoft, Meta, Google
Practice this problem

Problem Statement

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

 

Constraints:

  • 3 <= s.length <= 50
  • s consists of only lowercase English letters.

Approach Overview

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.

Approach 1: Sliding Window and Frequency Map

This approach uses a sliding window to dynamically track sequences of the same character and a frequency map to count occurrences of such sequences. The idea is to scan through the string, identify sequences where a character repeats, and use a frequency map to track how often these sequences appear. We are interested in sequences that appear at least three times.

The C solution uses a loop to iterate through the string, checking for sequences of identical characters. It keeps track of the longest such sequence and returns max_len - 2 if any sequence appears at least three times, or -1 otherwise.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Dynamic Programming

This approach uses dynamic programming to keep a matrix where DP[i][j] indicates whether substring s[i...j] is a special substring (formed by the same character). We will store the length of such substrings and check for their frequency throughout the matrix.

In this C solution, we initialize a DP table to find and store substrings that are comprised of only one type of character. By checking from each gap size, we derive substrings and see if they repeat. We adjust the maximum computed substring length if it repeats more than thrice.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), Space Complexity: O(n^2), where n is the length of the string.

Try this approach in the editor →

Approach 3: Binary Search + Sliding Window Counting

We notice that if there exists a special substring of length x that appears at least three times, then a special substring of length x-1 must also exist. This exhibits a monotonicity, so we can use binary search to find the longest special substring.

We define the left boundary of the binary search as l = 0 and the right boundary as r = n, where n is the length of the string. In each binary search, we take mid = \lfloor \frac{l + r + 1}{2} \rfloor. If a special substring of length mid exists, we update the left boundary to mid. Otherwise, we update the right boundary to mid - 1. During the binary search, we use a sliding window to count the number of special substrings.

Specifically, we design a function check(x) to indicate whether a special substring of length x that appears at least three times exists.

In the function check(x), we define a hash table or an array of length 26 named cnt, where cnt[i] represents the count of special substrings of length x composed of the i-th lowercase letter. We traverse the string s. If the current character is s[i], we move the pointer j to the right until s[j] neq s[i]. At this point, s[i cdots j-1] is a special substring of length x. We increase cnt[s[i]] by max(0, j - i - x + 1), and then update the pointer i to j.

After the traversal, we go through the array cnt. If there exists cnt[i] geq 3, it means a special substring of length x that appears at least three times exists, so we return true. Otherwise, we return false.

The time complexity is O((n + |\Sigma|) times log n), and the space complexity is O(|\Sigma|), where n is the length of the string s, and |\Sigma| represents the size of the character set. In this problem, the character set is lowercase English letters, so |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Counting

The time complexity is O(n)

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window and Frequency Map

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1).

Dynamic Programming

Time Complexity: O(n^2), Space Complexity: O(n^2), where n is the length of the string.

Binary Search + Sliding Window Counting—
Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window and Frequency MapO(n)O(n)Best general solution. Efficient for large strings and commonly expected in interviews.
Dynamic Programming (Run Length DP)O(n^2)O(n)Useful for understanding substring counting logic or when implementing a simpler but less optimized solution.

Video Solution

Find Longest Special Substring That Occurs Thrice I & II | Leetcode 2981 & 2982 | codestorywithMIK • codestorywithMIK • 10,104 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Longest Special Substring That Occurs Thrice I easy or hard?
The problem is rated Medium because the brute-force idea of checking all substrings is straightforward but inefficient. The challenge is recognizing that only runs of identical characters matter and converting the task into a counting problem. Once that observation is made, the optimized linear-time solution becomes manageable.
Find Longest Special Substring That Occurs Thrice I Python/Java solution
Python and Java implementations typically compute consecutive run lengths and store substring frequencies using dictionaries or arrays. Both languages can implement the optimal O(n) solution by iterating through runs and updating counts for each possible substring length. The logic remains identical across C++, Python, Java, and other languages.
How to solve Find Longest Special Substring That Occurs Thrice I in O(n)?
Traverse the string and compute lengths of consecutive identical-character segments. For each segment, count how many special substrings of each length can be formed and update a frequency map per character. Track the largest length whose frequency reaches three. Because the algorithm processes runs instead of generating all substrings, it achieves linear time complexity.
What is the best approach for Find Longest Special Substring That Occurs Thrice I?
The most efficient solution scans the string and groups consecutive identical characters into runs. Each run generates special substrings of different lengths, and a frequency counter tracks how many times each length appears. Once a substring length occurs at least three times, it becomes a candidate answer. This approach runs in O(n) time with O(n) auxiliary space.
Is Find Longest Special Substring That Occurs Thrice I asked at Google/Amazon/Meta?
Problems involving substring frequency, run-length encoding, and sliding window techniques frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. This problem specifically tests string analysis and counting strategies, which are common interview patterns.
What data structure is used in Find Longest Special Substring That Occurs Thrice I?
The main data structures are arrays or hash maps used to track how many times substrings of a specific length occur for each character. Combined with run-length tracking of the string, these structures allow constant-time updates and efficient counting.
What is the time complexity of Find Longest Special Substring That Occurs Thrice I?
The optimal implementation runs in O(n) time where n is the length of the string. Each character is processed once while building runs of identical characters and updating substring counts. Space complexity is O(n) for storing frequency information or run-length data.

Ready to solve this problem?

Practice Find Longest Special Substring That Occurs Thrice I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring with At Least K Repeating Characters

Next

Longest Substring Without Repeating Characters