Scale Engineer

Find Longest Special Substring That Occurs Thrice I

Med
#2660Time: O(N^3). The outer loop for length `L` runs `N` times. The character loop is constant (26). The inner loop for counting runs `O(N)` times. String creation and comparison take `O(L)` time. This gives a total complexity of `O(N * 26 * (L + N*L))`, which simplifies to `O(N^3)` as `L` can be up to `N`.Space: O(N), where N is the length of the string. This space is used to store the `specialStr` being checked, which can have a length up to N.
Patterns
Sliding WindowCounting
Algorithms
Binary Search
Data structures
Hash TableString

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible length for a special substring, from the largest possible down to the smallest. For each length, it checks every possible special substring (e.g., "aaa", "bbb", etc.) and counts its occurrences in the input string. The first length found to have a special substring appearing at least three times is the answer.

Algorithm

  1. Initialize n = s.length().
  2. Iterate through all possible lengths L from n down to 1.
  3. For each length L, iterate through all 26 lowercase English letters, c from 'a' to 'z'.
  4. Construct a special string specialStr of length L consisting only of character c.
  5. Initialize a counter count = 0.
  6. Iterate through the input string s with a sliding window of size L (from index i = 0 to n - L).
  7. For each window, extract the substring sub and check if it equals specialStr.
  8. If they are equal, increment count.
  9. After checking all windows, if count is 3 or more, it means we have found a valid special substring. Since we are iterating L from largest to smallest, this is the longest possible length. Return L immediately.
  10. If the loops complete without returning, no special substring occurs at least three times. Return -1.

Walkthrough

The algorithm iterates through possible lengths L from s.length() down to 1. For each length L, it iterates through all 26 lowercase English letters, from 'a' to 'z'. For each character c, it constructs a "special string" target of length L consisting only of character c. It then counts how many times this target string appears as a substring in the input string s. To count occurrences, it slides a window of size L across s and checks for equality with target. If the count for any target string is 3 or more, it means we have found the longest special substring that meets the criteria (since we are iterating L downwards). The algorithm can immediately return L. If the loops complete without finding such a substring, it means none exists, and the function returns -1.

class Solution {    public int maximumLength(String s) {        int n = s.length();        // Iterate from the largest possible length down to 1        for (int len = n; len >= 1; len--) {            // Check for each character 'a' through 'z'            for (char c = 'a'; c <= 'z'; c++) {                // Build the special string to search for                StringBuilder sb = new StringBuilder();                for (int k = 0; k < len; k++) {                    sb.append(c);                }                String specialStr = sb.toString();                                int count = 0;                // Count occurrences of the special string                for (int i = 0; i <= n - len; i++) {                    if (s.substring(i, i + len).equals(specialStr)) {                        count++;                    }                }                                // If found 3 or more times, this is the max length                if (count >= 3) {                    return len;                }            }        }        return -1;    }}

Complexity

Time

O(N^3). The outer loop for length `L` runs `N` times. The character loop is constant (26). The inner loop for counting runs `O(N)` times. String creation and comparison take `O(L)` time. This gives a total complexity of `O(N * 26 * (L + N*L))`, which simplifies to `O(N^3)` as `L` can be up to `N`.

Space

O(N), where N is the length of the string. This space is used to store the `specialStr` being checked, which can have a length up to N.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correct and guaranteed to find the solution.

Cons

  • The time complexity is cubic, which can be slow for larger constraints, although it passes for N <= 50.

  • It performs many redundant string comparisons.

Solutions

class Solution {private  String s;private  int n;public  int maximumLength(String s) {    this.s = s;    n = s.length();    int l = 0, r = n;    while (l < r) {      int mid = (l + r + 1) >> 1;      if (check(mid)) {        l = mid;      } else {        r = mid - 1;      }    }    return l == 0 ? -1 : l;  }private  boolean check(int x) {    int[] cnt = new int[26];    for (int i = 0; i < n;) {      int j = i + 1;      while (j < n && s.charAt(j) == s.charAt(i)) {        j++;      }      int k = s.charAt(i) - 'a';      cnt[k] += Math.max(0, j - i - x + 1);      if (cnt[k] >= 3) {        return true;      }      i = j;    }    return false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem