• Leetcode POTDs

Problem 2981 Find Longest Special Substring That Occurs Thrice I

Problem Statement

Link - Problem 2981

Question

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.

Solution

class Solution {
public:
    int maximumLength(string s) {
        map<string,int> freq;
        for(int i = 0; i<s.size(); i++){
            string temp;
            for(int j = i; j<s.size(); j++){
                if(temp.empty() || temp.back() == s[j]){
                    temp.push_back(s[j]);
                    freq[temp]++;
                }
                else
                    break;
            }
        }
        int ans = 0;
        for(auto f:freq){
            if(f.second>=3 && f.first.size() > ans)
                ans = f.first.size();
        }
        if(ans ==0)
            return -1;

        return ans;
    }
};

Complexity Analysis

| Algorithm                            | Time Complexity | Space Complexity |
| ------------------------------------ | --------------- | ---------------- |
| Dynamic Programming with Nested Loop | O(n^2)          | O(n)             |

Explanation

Intial Thoughts

To solve this problem, consider breaking down the string into substrings and checking if each substring is ‘special’. A special substring is one that consists of only a single character. Think of it like grouping similar letters together in a word. Start by generating all possible substrings of the given string. Then, filter out the special substrings by checking if all characters in the substring are the same. After that, count the frequency of each special substring to find the ones that occur at least thrice.

Intuitive Analysis

Imagine sliding a window over the string to generate substrings. Once you have all the substrings, use a frequency counter to keep track of how many times each special substring appears. Picture a dictionary where the keys are the substrings and the values are their frequencies. By iterating through this dictionary, you can find the longest special substring that occurs at least three times. If no such substring exists, return -1. This process involves systematically generating substrings, checking for special ones, counting their occurrences, and identifying the longest one that meets the criteria.

1. Intuition

• The problem requires finding the length of the longest special substring that occurs at least thrice in a given string.
• A special substring is one that consists of only a single character.
• To solve this problem, we need to generate all possible substrings of the given string and check if they are special.
• We can use a hashmap to store the frequency of each substring.
• The key insight is to only consider substrings that consist of the same character.
• This is because a special substring must be made up of only a single character.
• By iterating over the string and generating all possible substrings, we can find the longest special substring that occurs at least thrice.

2. Implementation

• We start by initializing an empty hashmap freq to store the frequency of each substring.
• We then iterate over the string using two nested loops to generate all possible substrings.
• For each substring, we check if it is special by comparing the current character with the previous character using temp.back() == s[j].
• If the substring is special, we increment its frequency in the hashmap using freq[temp]++.
• After generating all substrings, we iterate over the hashmap to find the longest special substring that occurs at least thrice using f.second>=3 && f.first.size() > ans.
• If such a substring is found, we update the answer ans with its length.
• Finally, we return the length of the longest special substring that occurs at least thrice, or -1 if no such substring is found.

Complexity Analysis

Time Complexity:

• The time complexity of the given algorithm is determined by the nested loop structure, where the outer loop iterates s.size() times and the inner loop also iterates up to s.size() times, resulting in a quadratic time complexity of O(n^2).
• The dominant operations are the nested loop iterations and the freq[temp]++ operation, which occurs within the inner loop, contributing to the overall time complexity.
• The Big O classification of O(n^2) is justified by the fact that the algorithm’s running time grows quadratically with the size of the input string s, making it less efficient for large inputs.

Space Complexity:

• The space complexity is determined by the memory usage of the freq map, which stores frequency of substrings in the input string s. In the worst case, the map can store up to s.size() unique substrings.
• The use of a map data structure to store frequency of substrings has a significant impact on the space complexity, as the map’s size can grow linearly with the size of the input string.
• The space complexity is classified as O(n) because the memory usage grows linearly with the size of the input string, where n represents the length of the input string s.

Proof of correctness

• Longest Special Substring That Occurs Thrice
• Direct Proof

Footnote

This question is rated as Medium difficulty.

Hints

The constraints are small.

Brute force checking all substrings.

Similar Questions:

$$

$$