Problem of The Day: Find Longest Special Substring That Occurs Thrice I

Problem Statement

Intuition

The problem involves identifying the longest substring that appears at least three times in the given string. The first thought is to leverage substring generation and frequency counting. By breaking the string into unique substrings of interest and analyzing their occurrence, we can efficiently solve the problem.

Approach

1. Identifying Unique Substrings:

   • Traverse the string using two pointers (start and end) to extract potential “special substrings” where characters differ at boundaries. These substrings are stored in a set to ensure uniqueness.

2. Sorting and Evaluation:

   • Sort the special substrings by their lengths in descending order to prioritize longer substrings during evaluation.

3. Sliding Window Frequency Check:

   • For each special substring, use a sliding window to identify all its occurrences in the string.
   • Track the count of occurrences using a Counter. If a substring appears at least three times and its length is greater than the current result, update the result.

4. Optimization:

   • The algorithm avoids unnecessary computations by processing substrings in order of their length and halting further checks when shorter substrings cannot improve the result.

Complexity

• Time complexity:

  • Identifying special substrings: \(O(n)\), where (n) is the length of the string.
  • Sliding window substring comparison: Worst-case (O(n^3)) for all substrings but optimized due to early exits and descending length order.
  • Sorting special substrings: \(O(k \log k)\), where (k) is the number of unique substrings.
  • Overall: Approx. \(O(n^3)\) in worst case but practically better for smaller substring sets.

• Space complexity:

  • Storage for special substrings: \(O(k)\).
  • Counter and additional variables: \(O(n)\).
  • Overall: \(O(k + n)\).

Code

from collections import Counter

class Solution:
    def maximumLength(self, s: str) -> int:
        start, end = 0, 0
        N = len(s)
        res = -1
        counter = Counter()
        special_strings = set()
        while end < N:
            if s[end] != s[start]:
                special_strings.add(s[start:end])
                start = end
            end += 1

        if end - start > 1:
            special_strings.add(s[start:end])

        sorted_special_strings = sorted(list(special_strings), key=lambda x: -len(x))

        for special_string in sorted_special_strings:
            window = len(special_string)
            while window > 0:
                start = 0
                target = special_string[start:start+window]
                for end in range(window - 1, N):
                    if s[start:end + 1] == target:
                        counter[target] += 1
                        if counter[target] >= 3 and window > res:
                            res = max(res, window)
                    start += 1
                window -= 1

        return res

Editorial

Approach 1: Brute-Force Approach

class Solution:
    def maximumLength(self, s: str) -> int:
        # Create a dictionary (equivalent of map in Python) to store the count of all substrings
        count = {}
        for start in range(len(s)):
            curr_string = (
                []
            )  # Use a list to store the characters of the current substring
            for end in range(start, len(s)):
                # If the string is empty, or the current character is equal to
                # the previously added character, then append it to the list.
                # Otherwise, break the iteration.
                if not curr_string or curr_string[-1] == s[end]:
                    curr_string.append(s[end])
                    curr_to_string = "".join(
                        curr_string
                    )  # Convert the list to a string
                    if curr_to_string in count:
                        count[curr_to_string] += 1
                    else:
                        count[curr_to_string] = 1
                else:
                    break

        # Create a variable ans to store the longest length of substring with
        # frequency at least 3.
        ans = 0
        for str, freq in count.items():
            if freq >= 3 and len(str) > ans:
                ans = len(str)

        if ans == 0:
            return -1
        return ans

Approach 2: Optimized Hashing

class Solution:
    def maximumLength(self, s: str) -> int:
        # Create a dictionary to store the count of all substrings.
        count = {}
        count_strings = 0
        for start in range(len(s)):
            character = s[start]
            substring_length = 0
            for end in range(start, len(s)):
                # If the string is empty, or the current character is equal to
                # the previously added character, then add it to the map.
                # Otherwise, break the iteration.
                if character == s[end]:
                    substring_length += 1
                    count[(character, substring_length)] = (
                        count.get((character, substring_length), 0) + 1
                    )
                else:
                    break

        # Create a variable ans to store the longest length of substring with
        # frequency atleast 3.
        ans = 0
        for i in count.items():
            length = i[0][1]
            if i[1] >= 3 and length > ans:
                ans = length
        if ans == 0:
            return -1
        return ans