Find Longest Special Substring That Occurs Thrice I

Medium
1762.

Find Longest Special Substring That Occurs Thrice I

Find Longest Special Substring That Occurs Thrice I is a medium coding problem on strings, hash table and binary search, asked in Amazon and Google interviews.

You are given a string s of lowercase letters.

A string is special if every character in it is the same — "ddd", "z" and "ff" are special, "abc" and "ccd" are not.

Return the length of the longest special substring of s that occurs at least three times (occurrences may overlap), or -1 if no special substring occurs three times.

Example 1

Input
s = "aaaa"
Output
2
Explanation
"aa" starts at indices 0, 1 and 2. "aaa" occurs only twice.

Example 2

Input
s = "abcdef"
Output
-1
Explanation
Every special substring is a single letter that occurs once.

Example 3

Input
s = "abcaba"
Output
1
Explanation
"a" occurs at indices 0, 3 and 5.

Constraints

  • 3 <= s.length <= 50
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var maximumLength = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Longest Special Substring That Occurs Thrice I Solution

Find Longest Special Substring That Occurs Thrice I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find Longest Special Substring That Occurs Thrice I is a medium coding problem on strings, hash table and binary search, asked in Amazon and Google interviews.

Problem statement

You are given a string s of lowercase letters.

A string is special if every character in it is the same — "ddd", "z" and "ff" are special, "abc" and "ccd" are not.

Return the length of the longest special substring of s that occurs at least three times (occurrences may overlap), or -1 if no special substring occurs three times.

Example 1

Input: s = "aaaa"
Output: 2
Explanation: "aa" starts at indices 0, 1 and 2. "aaa" occurs only twice.

Example 2

Input: s = "abcdef"
Output: -1
Explanation: Every special substring is a single letter that occurs once.

Example 3

Input: s = "abcaba"
Output: 1
Explanation: "a" occurs at indices 0, 3 and 5.

Constraints

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

Hints for Find Longest Special Substring That Occurs Thrice I

  1. Hint 1

    A special substring lives entirely inside one maximal run of a single repeated letter.

  2. Hint 2

    A run of letter c with length L contains the special string of length l exactly L - l + 1 times (for l <= L).

  3. Hint 3

    For every letter and every length, add those counts over all runs, and keep the largest length whose total reaches 3.

How to solve Find Longest Special Substring That Occurs Thrice I

Split s into maximal runs of one letter. Every occurrence of a special substring sits inside one run, and a run of length L contributes L - l + 1 occurrences of the length-l string of its letter. Summing those per (letter, length) gives every occurrence count directly.

Approach

  1. Walk s and cut it into maximal runs; for a run of letter c and length L, add L - l + 1 to count[c][l] for every l from 1 to L.
  2. Scan all (c, l) with count[c][l] >= 3 and keep the largest l.
  3. Return it, or -1 if there is none.

Why it works

Two different runs of the same letter are separated by another letter, so no occurrence spans two runs, and inside a run every window of length l is an occurrence. The sum therefore counts every occurrence exactly once.

Complexity

  • Time — O(n^2) at worst (the sum of the squared run lengths)
  • Space — O(26 * n)

Pitfalls

  • Occurrences may overlap: "aaaa" contains "aa" three times.
  • Runs of the same letter in different places all add to the same counter — in "aabaab" the two runs of a together give "a" four times.

Reference solution

Python

def maximumLength(s: str) -> int:
    n = len(s)
    count = [[0] * (n + 2) for _ in range(26)]
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        run = j - i
        c = ord(s[i]) - 97
        for l in range(1, run + 1):
            count[c][l] += run - l + 1
        i = j
    best = -1
    for c in range(26):
        for l in range(1, n + 1):
            if count[c][l] >= 3 and l > best:
                best = l
    return best

Java

public static int maximumLength(String s) {
    int n = s.length();
    int[][] count = new int[26][n + 2];
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && s.charAt(j) == s.charAt(i)) j++;
        int run = j - i, c = s.charAt(i) - 'a';
        for (int l = 1; l <= run; l++) count[c][l] += run - l + 1;
        i = j;
    }
    int best = -1;
    for (int c = 0; c < 26; c++)
        for (int l = 1; l <= n; l++)
            if (count[c][l] >= 3 && l > best) best = l;
    return best;
}

C++

int maximumLength(string s) {
    int n = s.size();
    vector<vector<int>> count(26, vector<int>(n + 2, 0));
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;
        int run = j - i, c = s[i] - 'a';
        for (int l = 1; l <= run; l++) count[c][l] += run - l + 1;
        i = j;
    }
    int best = -1;
    for (int c = 0; c < 26; c++)
        for (int l = 1; l <= n; l++)
            if (count[c][l] >= 3 && l > best) best = l;
    return best;
}

JavaScript

var maximumLength = function(s) {
    var n = s.length;
    var count = [];
    for (var c = 0; c < 26; c++) {
        count.push(new Array(n + 2).fill(0));
    }
    var i = 0;
    while (i < n) {
        var j = i;
        while (j < n && s[j] === s[i]) j++;
        var run = j - i, ch = s.charCodeAt(i) - 97;
        for (var l = 1; l <= run; l++) count[ch][l] += run - l + 1;
        i = j;
    }
    var best = -1;
    for (var c2 = 0; c2 < 26; c2++) {
        for (var l2 = 1; l2 <= n; l2++) {
            if (count[c2][l2] >= 3 && l2 > best) best = l2;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets