Leetcode – Largest Substring Between Two Equal Characters Solution

Spread the love

The “Largest Substring Between Two Equal Characters” problem from Leetcode is a classic example of string manipulation and analysis. It serves as a fantastic playground for those wishing to deepen their understanding of strings, substrings, and algorithms that deal with text data. While it might appear straightforward at first glance, there are subtle nuances that offer fertile ground for discussion.

In this exhaustive article, we will break down the problem description, walk through multiple approaches to solve it, evaluate their time and space complexity, and implement them in Python. Along the way, we will also point out any related problems, useful programming paradigms, and best practices.

Problem Description

The problem description on Leetcode is as follows:

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there are no such substrings, return -1.

Example

maxLengthBetweenEqualCharacters("aa")    # Output: 0
maxLengthBetweenEqualCharacters("abca")  # Output: 2
maxLengthBetweenEqualCharacters("cbzxy") # Output: -1

Approach 1: Brute Force

Algorithm

  1. Initialize a variable, max_length, to store the maximum length of the substring between two equal characters. Set it to -1 initially.
  2. Loop through each character in the string s.
  • For each character, find its last occurrence in the string.
  • Calculate the length of the substring between these two equal characters.
  • Update max_length if this length is greater than the current max_length.

Python Code

def maxLengthBetweenEqualCharacters(s: str) -> int:
    max_length = -1
    
    for i, char in enumerate(s):
        last_occurrence = s.rfind(char)
        
        if last_occurrence != i:
            max_length = max(max_length, last_occurrence - i - 1)
            
    return max_length

Time Complexity

The time complexity of this approach is O(n^2) because we loop through each character in the string ss and also use rfind method, which itself has a time complexity of O(n).

Space Complexity

The space complexity is O(1) as we are not using any additional data structures.

Approach 2: Using Dictionary to Store First Occurrence

Algorithm

  1. Create a dictionary to map each character to its first occurrence in the string s.
  2. Initialize max_length to -1.
  3. Loop through the string s and for each character:
  • If the character is not in the dictionary, add it with its index.
  • If the character is in the dictionary, calculate the length of the substring between the two occurrences and update max_length.

Python Code

def maxLengthBetweenEqualCharacters(s: str) -> int:
    first_occurrence = {}
    max_length = -1
    
    for i, char in enumerate(s):
        if char not in first_occurrence:
            first_occurrence[char] = i
        else:
            max_length = max(max_length, i - first_occurrence[char] - 1)
            
    return max_length

Time Complexity

The time complexity of this approach is O(n) because we loop through the string ss only once.

Space Complexity

The space complexity is O(n) because, in the worst case, we may store each character in the dictionary.

Discussion: Two-pointer Technique

While the two-pointer technique is not directly applicable to this problem, problems related to substrings and subsequences often benefit from it. Therefore, knowing such a technique might be helpful for solving other similar problems more efficiently.

Related Problems

  1. Longest Palindromic Substring: This problem also deals with substrings and asks for the longest palindromic substring in a given string.
  2. Longest Substring Without Repeating Characters: This problem asks for the longest substring without any repeating characters.

Conclusion

While the brute force solution is straightforward to implement, its time complexity makes it less suitable for long strings. On the other hand, the dictionary-based solution provides a more efficient way to solve the problem with O(n) time complexity and O(n) space complexity.

Leave a Reply