2981. Find Longest Special Substring That Occurs Thrice I

[mah-shamim]

Topics: Hash Table, String, Binary Search, Sliding Window, Counting

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 = "abcdef"
• 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.

Hint:

1. The constraints are small.
2. Brute force checking all substrings.

[mah-shamim]

We can use a brute force approach due to the small constraints of s (length of up to 50). We'll:

1. Iterate over possible lengths of substrings (from longest to shortest).
2. Check all substrings of the given length and count their occurrences.
3. If a substring occurs at least three times, check if it is special (made of one repeated character).
4. Return the length of the longest such substring. If no substring satisfies the conditions, return -1.

Let's implement this solution in PHP: 2981. Find Longest Special Substring That Occurs Thrice I

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLength($s) {
    $n = strlen($s);

    // Iterate over substring lengths from longest to shortest
    for ($len = $n; $len >= 1; $len--) {
        $countMap = [];

        // Sliding window to collect substrings of length $len
        for ($i = 0; $i <= $n - $len; $i++) {
            $substring = substr($s, $i, $len);

            // Count the occurrences of each substring
            if (!isset($countMap[$substring])) {
                $countMap[$substring] = 0;
            }
            $countMap[$substring]++;
        }

        // Check if any special substring occurs at least 3 times
        foreach ($countMap as $substring => $count) {
            if ($count >= 3 && isSpecial($substring)) {
                return $len; // Return the length of the substring
            }
        }
    }

    // If no special substring occurs at least 3 times
    return -1;
}

/**
 * Helper function to check if a substring is special
 *
 * @param $substring
 * @return bool
 */
function isSpecial($substring) {
    $char = $substring[0];
    for ($i = 1; $i < strlen($substring); $i++) {
        if ($substring[$i] !== $char) {
            return false;
        }
    }
    return true;
}

// Test cases
echo maximumLength("aaaa") . "\n"; // Output: 2
echo maximumLength("abcdef") . "\n"; // Output: -1
echo maximumLength("abcabcabc") . "\n"; // Output: 1
?>

Explanation:

1. Outer Loop: We iterate over the possible lengths of substrings, starting with the longest. This ensures we return the longest special substring as soon as we find it.
2. Sliding Window: For each substring length, we use a sliding window approach to extract all substrings of that length.
3. Counting Substrings: We use an associative array ($countMap) to store and count occurrences of each substring.
4. Checking Special: A helper function isSpecial checks if the substring is made up of only one repeated character.
5. Returning the Result: If a valid substring is found, we return its length; otherwise, we return -1.

Complexity

• Time Complexity: O(n³) in the worst case because we:
  1. Iterate over n substring lengths.
  2. Extract O(n) substrings for each length.
  3. Check if each substring is special, which takes O(n) time.
• Space Complexity: O(n²) due to the substring counting map.

This brute force approach is feasible given the constraints (n <= 50).

[topugit]

Thanks to solving the problem of finding the longest special substring that occurs at least three times in a given string s

[mah-shamim]

Thanks