2981. Find Longest Special Substring That Occurs Thrice I

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 01:

class Solution {
 public:
  int maximumLength(string s) {
    const int stringLength = s.length();
    int maxLength = -1;
    int currentLength = 0;
    char previousChar = '@';
    // counts[charIndex][repetition] := the frequency of ('a' + charIndex) repeating `repetition` times
    vector<vector<int>> charFrequency(26, vector<int>(stringLength + 1));

    for (const char currentChar : s) {
      if (currentChar == previousChar) {
        ++charFrequency[currentChar - 'a'][++currentLength];
      } else {
        currentLength = 1;
        ++charFrequency[currentChar - 'a'][currentLength];
        previousChar = currentChar;
      }
    }

    for (const vector<int>& frequency : charFrequency) {
      maxLength = max(maxLength, getMaxFreq(frequency, stringLength));
    }

    return maxLength;
  }

 private:
  // Returns the maximum frequency that occurs more than three times.
  int getMaxFreq(const vector<int>& frequency, int maxFrequency) {
    int occurrences = 0;
    for (int freq = maxFrequency; freq >= 1; --freq) {
      occurrences += frequency[freq];
      if (occurrences >= 3)
        return freq;
    }
    return -1;
  }
};

class Solution:
    def maximumLength(self, s: str) -> int:
        stringLength = len(s)
        maxLength = -1
        currentLength = 0
        previousChar = '@'
        # charFrequency[charIndex][repetition] := frequency of ('a' + charIndex) repeating `repetition` times
        charFrequency = [[0] * (stringLength + 1) for _ in range(26)]

        for currentChar in s:
            if currentChar == previousChar:
                currentLength += 1
                charFrequency[ord(currentChar) - ord('a')][currentLength] += 1
            else:
                currentLength = 1
                charFrequency[ord(currentChar) - ord('a')][currentLength] += 1
                previousChar = currentChar

        for frequency in charFrequency:
            maxLength = max(maxLength, self.getMaxFreq(frequency, stringLength))

        return maxLength

    # Returns the maximum frequency that occurs more than three times.
    def getMaxFreq(self, frequency: list[int], maxFrequency: int) -> int:
        occurrences = 0
        for freq in range(maxFrequency, 0, -1):
            occurrences += frequency[freq]
            if occurrences >= 3:
                return freq
        return -1

Time Complexity

• Traversal of the String:
  • The string s is traversed once to compute the character frequencies.
  • This traversal takes \(O(n)\), where \(n\) is the length of the string.
• Processing Each Character’s Frequency:
  • For each of the 26 characters, the getMaxFreq function iterates over the possible frequencies (at most \(n\)).
  • This takes \(O(26 \cdot n)\), simplified to \(O(n)\) because 26 is a constant.
• Overall Time Complexity:

  The total time complexity is \(O(n)\), dominated by the string traversal and frequency processing.

Space Complexity

• Frequency Storage:
  • The charFrequency 2D vector stores frequency data for 26 characters and up to \(n + 1\) repetitions for each character.
  • This requires \(O(26 \cdot (n + 1))\), simplified to \(O(n)\), as 26 is a constant.
• Other Variables:
  • Variables like maxLength, currentLength, previousChar, and loop variables require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the frequency storage.