Find Longest Special Substring That Occurs Thrice I

class Solution {
public:
    int findMaxLength(string str) {
        map<pair<char, int>, int> substringCount;
        int maxLen = 0;
        for (int i = 0; i < str.size(); i++) {
            char currentChar = str[i];
            maxLen = 0;
            for (int j = i; j < str.size(); j++) {
                if (currentChar == str[j]) {
                    maxLen++;
                    substringCount[{currentChar, maxLen}]++;
                } else {
                    break;
                }
            }
        }

        int result = -1;
        for (auto pair : substringCount) {
            int length = pair.first.second;
            if (pair.second >= 3 && length > result) result = length;
        }

        return result;
    }
};

The given C++ code solves the problem of finding the longest substring that consists of the same character and appears at least three times in the given string. Here's a structured explanation of how it achieves this:

• The function findMaxLength accepts a string str as an argument and initializes a map substringCount to track the frequency of each substring that consists of the same character.

• It employs two nested loops to explore all possible substrings starting with each character in the string. The outer loop iterates over each character of the string, and the inner loop extends the substring as long as consecutive characters match the starting character.

• Every time a matching character is found, the length of the current substring increases (maxLen++). A pair consisting of the current character and its length is used as a key in substringCount map to count its occurrences in the entire string.

• If the character does not match or the end of the string is reached, the inner loop breaks.

• After the nested loops complete, the function checks for the maximum length among substrings that appeared at least three times using a post-processing step iterating over the substringCount map.

• It compares the number of occurrences of each unique substring and updates the result with the maximum length of those substrings that appeared three or more times.

• The value -1 is returned if no such substring exists. Otherwise, the length of the longest such substring that meets the criteria is returned.

class Solution {

    public int findMaxLen(String str) {
        // Store count of substring occurrences
        Map<Pair<Character, Integer>, Integer> frequencyMap = new HashMap<>();
        int maxLen = 0;

        for (int i = 0; i < str.length(); i++) {
            char currentChar = str.charAt(i);
            maxLen = 0;

            for (int j = i; j < str.length(); j++) {
                // Increase count if characters match
                if (currentChar == str.charAt(j)) {
                    maxLen++;
                    Pair<Character, Integer> key = new Pair<>(
                        currentChar,
                        maxLen
                    );
                    frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
                } else {
                    break;
                }
            }
        }

        // Finding longest substring where frequency is at least 3
        int maximum = -1;
        for (Map.Entry<
            Pair<Character, Integer>,
            Integer
        > entry : frequencyMap.entrySet()) {
            int length = entry.getKey().getValue();
            if (entry.getValue() >= 3 && length > maximum) {
                maximum = length;
            }
        }

        return maximum;
    }
}

The solution provided finds the length of the longest special substring that appears three times or more in a given string. The method findMaxLen is implemented within the class Solution. The approach involves the following steps:

1. A HashMap named frequencyMap is used to store occurrences of each substring composed of the same character, where the key is a pair of the character and its length, and the value is the frequency of this substring.
2. Initialize the variable maxLen to track the length of the current substring being considered.
3. Utilize a nested loop structure to iterate over the string. For each character at index i, find substrings that start with this character and consist only of this character, updating the frequencyMap accordingly.
4. In the inner loop, if the current character matches, increase maxLen and update the frequencyMap. If it does not match, break out of the inner loop.
5. Outside the loops, search through the entries in the frequencyMap to find the maximum length of any substring that occurs three times or more.

Finally, return -1 if no such substring exists, or return the length of the longest such substring otherwise. This algorithm efficiently maps out all possible special substrings and checks their frequencies to find the one satisfying the given condition.

class Solution:
    def maxRepeatingSubstring(self, input_str: str) -> int:
        # Dictionary for substring tracking based on frequency of occurrence.
        substring_counter = {}
        for idx in range(len(input_str)):
            current_char = input_str[idx]
            cur_substr_len = 0
            for j in range(idx, len(input_str)):
                # Continue counting if the substring characters match. Otherwise, stop.
                if current_char == input_str[j]:
                    cur_substr_len += 1
                    substring_key = (current_char, cur_substr_len)
                    substring_counter[substring_key] = (
                        substring_counter.get(substring_key, 0) + 1
                    )
                else:
                    break

        # Variable to store the maximum length of substrings with at least 3 occurrences.
        max_length = -1
        for key, val in substring_counter.items():
            substring_len = key[1]
            if val >= 3 and substring_len > max_length:
                max_length = substring_len

        return max_length

The Python solution presented is designed to find the maximum length of a repeating character subsequence in a given string that appears at least three times. Here's how you can understand and utilize the solution:

• Initialize a dictionary, substring_counter, to track the occurrence of each possible substring.
• Iterate over the input string using two nested loops:
  • The outer loop identifies the starting index of a potential repeating subsequence.
  • The inner loop extends the length of the subsequence as long as consecutive characters match the character at the starting index.
  • Create a tuple, substring_key, which consists of the current character and the length of the subsequence. Update the substring_counter dictionary to count occurrences of each substring.
• After constructing the dictionary, initialize max_length with a value of -1, which serves as the default for cases where no suitable substring is found.
• Traverse items in substring_counter. If a substring occurs at least three times and its length is greater than max_length, update max_length.
• Return the value of max_length, which is either the maximum length of a suitable repeating substring or -1 if no such substring exists.

Keep the following points in mind when implementing or adapting this code:

• Ensure there is appropriate error handling, particularly for edge cases like an empty string.
• The time complexity is primarily determined by the nested loops, which can lead to performance issues with large input strings. Consider optimizations if performance is a concern.