Teaching Kids Programming – Largest Substring Between Two Equal Characters (Brute Force, Find/Index)

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 Brute Force, Find/Index

We can brute force each pair of characters and then compare to see if it is equal, if yes, we count the number of the letters between (length of substring).

1
2
3
4
5
6
7
8
9

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        ans = -1
        n = len(s)
        for i in range(n):
            for j in range(i):
                if s[i] == s[j]:
                    ans = max(ans, i - j - 1)
        return ans

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        ans = -1
        n = len(s)
        for i in range(n):
            for j in range(i):
                if s[i] == s[j]:
                    ans = max(ans, i - j - 1)
        return ans

This takes O(N^2) time and O(1) space.

Since the given string contains only all lowercase letters, we can iterate from ‘a’ to ‘z’ and find the left-most and right-most index. This takes O(N) time, and O(1) space. The find returns -1 if substring not found while the index function throws exception when a substring is not in the string.

1
2
3
4
5
6
7
8
9

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        ans = -1
        for c in string.ascii_lowercase:
            right = s.rfind(c)
            if right != -1:
                left = s.find(c) # s.index(c) is also good
                ans = max(ans, right - left - 1)
        return ans

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        ans = -1
        for c in string.ascii_lowercase:
            right = s.rfind(c)
            if right != -1:
                left = s.find(c) # s.index(c) is also good
                ans = max(ans, right - left - 1)
        return ans

And, we can use one-liner together with the max function.

1
2
3

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        return max((s.rfind(c) - s.find(c) - 1 for c in string.ascii_lowercase), default=-1)

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        return max((s.rfind(c) - s.find(c) - 1 for c in string.ascii_lowercase), default=-1)

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) —