Teaching Kids Programming – Largest Substring Between Two Equal Characters (Hash Map)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1. A substring is a contiguous sequence of characters within a string.

Example 1:
Input: s = “aa”
Output: 0
Explanation: The optimal substring here is an empty substring between the two ‘a’s.

Example 2:
Input: s = “abca”
Output: 2
Explanation: The optimal substring here is “bc”.

Example 3:
Input: s = “cbzxy”
Output: -1
Explanation: There are no characters that appear twice in s.

Constraints:
1 <= s.length <= 300
s contains only lowercase English letters.

Hints:
Try saving the first and last position of each character
Try finding every pair of indexes with equal characters

Largest Substring Between Two Equal Characters via Hash Table/Map

We can use a hash table to remember the leftmost/first index that a character appears in the string when we iterate over the characters via the enumerate function. Then the subsequent same characters, we count the number of the characters of the substring between its first occurrence and the current index, and meantime we update the longest substring.

The time/space complexity is O(N) where N is the number of the characters in the given string. Since the string is all lowercase, then the space complexity is O(1) as the upperbound of the number of the entries in the hash table is 26, which is O(1) constant.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        seen = {}
        ans = -1
        for i, v in enumerate(s):
            if v in seen:
                ans = max(ans, i - seen[v] - 1)
            else:
                seen[v] = i
        return ans

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        seen = {}
        ans = -1
        for i, v in enumerate(s):
            if v in seen:
                ans = max(ans, i - seen[v] - 1)
            else:
                seen[v] = i
        return ans

Largest Substring Between Two Equal Characters

• Compute the Largest Substring Between Two Equal Characters using Hash Table
• Teaching Kids Programming - Largest Substring Between Two Equal Characters (Hash Map)
• Teaching Kids Programming - Largest Substring Between Two Equal Characters (Brute Force, Find/Index)

–EOF (The Ultimate Computing & Technology Blog) —