Find Longest Special Substring That Occurs Thrice 1

Problem

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.

Examples

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "a̲a̲aa", "aa̲a̲a", and "aaa̲a̲".
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 "a̲bcaba", "abca̲ba", 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.

Solution

Method 1 - Naive

This involves generating all possible substrings which takes O(n^2) time and counting their occurrences in original string takes O(n) time, resulting in overall time complexity of O(n^3). Then, if the count is more than 3, we keep track of the max length of substring for our answer. This is super inefficient.

Method 2 - Count length of all special substrings

Identify Special Substrings:
- A special substring is defined as a sequence of identical characters.
- For example, in "aaabbbaaa", the special substrings are "aaa", "bbb", and another "aaa".
Track Occurrences of Each Special Substring:
- Use a dictionary to record the frequency of each special substring.
- Iterate through all possible special substrings to identify and count each one.
Determine the Longest Special Substring Meeting the Criteria:
- From the dictionary, identify the longest special substring that appears at least three times.
- If no such substring exists, return -1.

Code

Java

public class Solution {
    public int maximumLength(String s) {
        // Dictionary to store occurrences of special substrings
        Map<String, Integer> specialCounts = new HashMap<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            int j = i;
            // Find all special substrings starting at index i
            while (j < n && s.charAt(j) == s.charAt(i)) {
                // Current special substring
                String specialSub = s.substring(i, j + 1);
                specialCounts.put(specialSub, specialCounts.getOrDefault(specialSub, 0) + 1);
                j++;
            }
        }

        // Find the longest special substring occurring at least thrice
        int longestLength = -1;
        for (Map.Entry<String, Integer> entry : specialCounts.entrySet()) {
            if (entry.getValue() >= 3) {
                longestLength = Math.max(longestLength, entry.getKey().length());
            }
        }

        return longestLength;
    }

}

Python

class Solution:
    def maximumLength(self, s: str) -> int:
        # Dictionary to store occurrences of special substrings
        special_counts = {}
        n = len(s)

        for i in range(n):
            j = i
            # Find all special substrings starting at index i
            while j < n and s[j] == s[i]:
                # Current special substring
                special_sub = s[i:j + 1]
                if special_sub in special_counts:
                    special_counts[special_sub] += 1
                else:
                    special_counts[special_sub] = 1
                j += 1

        # Find the longest special substring occurring at least thrice
        longest_length = -1
        for special_sub, count in special_counts.items():
            if count >= 3:
                longest_length = max(longest_length, len(special_sub))

        return longest_length

Complexity

⏰ Time complexity: O(n^2) - We have nested loop, where the outer loop iterates over each starting position i of the string and the inner loop iterates to extend the substring until it encounters a different character.
In the worst case, the inner loop may run for all characters of the same type starting from position i. For example, in a string like "aaaa", the inner loop would run multiple times as i increases.
🧺 Space complexity: O(n^2)

Method 3 - Keep track of top 3 frequency of special strings

We need to find the length of the longest special substring (a substring made up of only one character) in a string s that appears at least thrice.

Now, for the string aaabbccd, what is the length of the longest special string (without caring about frequency) ? It is is 3 for character a.

Now, lets try to solve the frequency case. All, we need is the special string, that occurs at least thrice. The beauty of special string is that all characters are same. So, suppose we found special substrings in a string with length 6, 5, 4 and 2, we can easily say that substring of length 4 occurs thrice, which is what we want. So, we can discard length of special string which is 2.

We can use three variables (m1, m2, m3) to keep track of the three longest lengths of special substrings for the current character denoting first maximum, second and third maximum.

Tracking the three maximum lengths (m1, m2, m3) is essential because the problem requires identifying the longest special substring that occurs at least three times.

So, here is our approach:

Outer Loop: Iterate over each character ch from ‘a’ to ‘z’. Track the 3 maximum lengths of this character - m1, m2 and m3
Inner Loop: Iterate through the string s to find continuous substrings of the current character.
- When a new segment of the current character is found, update these lengths if the segment is longer than any of the three tracked lengths.
- For example, when examining a segment of the current character:
  - If currLen is greater than m1, then update m1, m2, and m3 accordingly.
  - Similarly update m2 if currLen is greater than m2 but less than m1.
  - Otherwise, update m3 if currLen is greater than m1 but less than m1 and m2.
- Update Result: After processing the current character, update the result (ans) with the maximum valid length found (m1).
Final Check: If no valid segment was found (i.e., ans remains 0), return -1. Otherwise, return the recorded longest length (ans).

Code

Java

public class Solution {
    public int maximumLength(String s) {
        int n = s.length();
        int ans = -1;

        for (char ch = 'a'; ch <= 'z'; ch++) {
            int m1 = 0, m2 = 0, m3 = 0;
            int i = 0;

            while (i < n) {
                if (ch == s.charAt(i)) {
                    int j = i, currLen = 0;

                    while (i < n && s.charAt(i) == s.charAt(j)) {
                        currLen++;
                        if (m1 < currLen) {
                            m3 = m2;
                            m2 = m1;
                            m1 = currLen;
                        } else if (m2 < currLen) {
                            m3 = m2;
                            m2 = currLen;
                        } else if (m3 < currLen) {
                            m3 = currLen;
                        }
                        i++;
                    }
                } else {
                    i++;
                }
            }
            ans = Math.max(ans, m3);
        }

        return ans == 0 ? -1 : ans;
    }
}

Python

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        ans = -1
        
        for ch in "abcdefghijklmnopqrstuvwxyz":
            m1, m2, m3 = 0, 0, 0
            i = 0
            
            while i < n:
                if ch == s[i]:
                    j = i
                    curr_len = 0
                    
                    while i < n and s[i] == s[j]:
                        curr_len += 1
                        if m1 < curr_len:
                            m3 = m2
                            m2 = m1
                            m1 = curr_len
                        elif m2 < curr_len:
                            m3 = m2
                            m2 = curr_len
                        elif m3 < curr_len:
                            m3 = curr_len
                        i += 1
                else:
                    i += 1
            
            ans = max(ans, m3)
        
        return -1 if ans == 0 else ans

Complexity

⏰ Time complexity: O(26 * n) => O(n) as there are 26 letters in the English alphabet and n is the length of the string.
🧺 Space complexity: O(1) because we are using a fixed amount of extra space.

Method 4 - Track top 3 frequencies - time optimized

Instead of going through the string character by character 26 times, we can make it 1 pass.

Here is the approach:

Initialization:
- The store array keeps track of the three longest lengths of continuous substrings for each character from ‘a’ to ‘z’.
Single Pass:
- By iterating through the string once, this approach ensures optimal performance.
Tracking Lengths:
- For each character, calculate the lengths of continuous substrings in real-time.
- Update the maximum lengths dynamically as we encounter longer sequences.
Updating Global Maximum:
- For each sequence of characters, update the global maximum length (ans) based on the longest sequences found.
Edge Handling:
- If no valid substring is found (i.e., ans remains 0), return -1. Otherwise, return ans.

Code

Java

public class Solution {
    public int maximumLength(String s) {
        int n = s.length();
        
        // Global max length
        int ans = 0;
        // freq: array for tracking m3, m2, m1 for each character (a to z)
        int[][] freq = new int[26][3];

        // Iterate only once
        for (int i = 0; i < n;) {
            int j = i, cnt = 0;

            // Bring those m3, m2, m1 of current char in string
            int m1 = freq[s.charAt(i) - 'a'][0];
            int m2 = freq[s.charAt(i) - 'a'][1];
            int m3 = freq[s.charAt(i) - 'a'][2];

            // Continue j pointer till the condition
            for (; j < n && s.charAt(j) == s.charAt(i); j++) {
                cnt++;
                if (cnt > m1) {
                    m3 = m2;
                    m2 = m1;
                    m1 = cnt;
                } else if (m2 < cnt) {
                    m3 = m2;
                    m2 = cnt;
                } else if (cnt > m3) {
                    m3 = cnt;
                }
            }

            freq[s.charAt(i) - 'a'][0] = m1;
            freq[s.charAt(i) - 'a'][1] = m2;
            freq[s.charAt(i) - 'a'][2] = m3;
            
            i = j;
            ans = Math.max(ans, m3);
        }

        return ans == 0 ? -1 : ans;
    }
}

Python

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)

        # Global max length
        ans = 0
        # freq: array for tracking m3, m2, m1 for each character (a to z)
        freq = [[0] * 3 for _ in range(26)]

        # Iterate only once
        i = 0
        while i < n:
            j, cnt = i, 0

            # Bring those m3, m2, m1 of current char in string
            m1, m2, m3 = freq[ord(s[i]) - ord('a')]

            # Continue j pointer till the condition
            while j < n and s[j] == s[i]:
                cnt += 1
                if cnt > m1:
                    m3 = m2
                    m2 = m1
                    m1 = cnt
                elif cnt > m2:
                    m3 = m2
                    m2 = cnt
                elif cnt > m3:
                    m3 = cnt
                j += 1

            freq[ord(s[i]) - ord('a')] = [m1, m2, m3]

            i = j
            ans = max(ans, m3)

        return -1 if ans == 0 else ans

Complexity

⏰ Time complexity: O(n), as we traverse the string only once.
🧺 Space complexity: O(26 * 3) => O(1), since the storage requirement is constant and independent of the input size.

Problem#

Examples#

Solution#

Method 1 - Naive#

Method 2 - Count length of all special substrings#

Code#

Java#

Python#

Complexity#

Method 3 - Keep track of top 3 frequency of special strings#

Code#

Java#

Python#

Complexity#

Method 4 - Track top 3 frequencies - time optimized#

Code#

Java#

Python#

Complexity#

Problem

Examples

Solution

Method 1 - Naive

Method 2 - Count length of all special substrings

Code

Java

Python

Complexity

Method 3 - Keep track of top 3 frequency of special strings

Code

Java

Python

Complexity

Method 4 - Track top 3 frequencies - time optimized

Code

Java

Python

Complexity