Compute the Largest Substring Between Two Equal Characters using Hash Table

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.

Example 4:
Input: s = “cabbac”
Output: 4
Explanation: The optimal substring here is “abba”. Other non-optimal substrings include “bb” and “”.

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

Using Hash Table to Compute the Largest SubString between Two Same Characters in a String

We can use a hash table to store the first seen position of a character. Then, if we see the same character we know the substring length. And sure we can compute the maximum substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        unordered_map<char, int> data;
        int ans = -1;
        for (auto i = 0; i < s.size(); ++ i) {
            if (data.count(s[i])) {
                ans = max(ans, i - data[s[i]] - 1);
            } else {
                data[s[i]] = i;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        unordered_map<char, int> data;
        int ans = -1;
        for (auto i = 0; i < s.size(); ++ i) {
            if (data.count(s[i])) {
                ans = max(ans, i - data[s[i]] - 1);
            } else {
                data[s[i]] = i;
            }
        }
        return ans;
    }
};

The time complexity is O(N) and the space complexity is also O(N) as we are using a hash set.

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