Skip to content

1624. Largest Substring Between Two Equal Characters

SourceWeekly Contest 211 Q1DifficultyEasyRating1281

Description

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.

Solutions

Solution 1: Array

Thinking

The length between two equal letters is the gap between that letter's first occurrence and a later one. The string is short, but keeping only the first index of each letter already yields a linear solution.

On seeing a character again, update the answer with \(i - d[j] - 1\) and do not overwrite the first index, so the span stays maximal.

Because \(s\) contains only lowercase letters, a length-\(26\) array is enough; if nothing appears twice, the answer stays \(-1\).

Since \(s\) contains only lowercase English letters, we can use an array \(d\) of length \(26\) to store the first index of each character, initially filled with \(-1\).

Traverse \(s\). For the character \(c\) at index \(i\), let \(j\) be the offset of \(c\) from a. If \(d[j] = -1\), this is the first time we see \(c\), so set \(d[j] = i\); otherwise update the answer with \(i - d[j] - 1\), i.e. \(ans = \max(ans, i - d[j] - 1)\).

The time complexity is \(O(n)\), and the space complexity is \(O(C)\), where \(n\) is the length of \(s\) and \(C = 26\) is the size of the alphabet.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        d = [-1] * 26
        ans = -1
        for i, c in enumerate(s):
            j = ord(c) - ord("a")
            if d[j] == -1:
                d[j] = i
            else:
                ans = max(ans, i - d[j] - 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int[] d = new int[26];
        Arrays.fill(d, -1);
        int ans = -1;
        for (int i = 0; i < s.length(); ++i) {
            int j = s.charAt(i) - 'a';
            if (d[j] == -1) {
                d[j] = i;
            } else {
                ans = Math.max(ans, i - d[j] - 1);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        vector<int> d(26, -1);
        int ans = -1;
        for (int i = 0; i < s.size(); ++i) {
            int j = s[i] - 'a';
            if (d[j] == -1) {
                d[j] = i;
            } else {
                ans = max(ans, i - d[j] - 1);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maxLengthBetweenEqualCharacters(s string) int {
    d := make([]int, 26)
    for i := range d {
        d[i] = -1
    }
    ans := -1
    for i := range s {
        j := int(s[i] - 'a')
        if d[j] == -1 {
            d[j] = i
        } else {
            ans = max(ans, i-d[j]-1)
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maxLengthBetweenEqualCharacters(s: string): number {
    const d = Array(26).fill(-1);
    let ans = -1;
    for (let i = 0; i < s.length; ++i) {
        const j = s.charCodeAt(i) - 97;
        if (d[j] === -1) {
            d[j] = i;
        } else {
            ans = Math.max(ans, i - d[j] - 1);
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn max_length_between_equal_characters(s: String) -> i32 {
        let s = s.as_bytes();
        let mut d = [-1; 26];
        let mut ans = -1;
        for i in 0..s.len() {
            let j = (s[i] - b'a') as usize;
            if d[j] == -1 {
                d[j] = i as i32;
            } else {
                ans = ans.max(i as i32 - d[j] - 1);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxLengthBetweenEqualCharacters(char* s) {
    int d[26];
    memset(d, -1, sizeof(d));
    int ans = -1;
    for (int i = 0; s[i]; ++i) {
        int j = s[i] - 'a';
        if (d[j] == -1) {
            d[j] = i;
        } else {
            ans = max(ans, i - d[j] - 1);
        }
    }
    return ans;
}

Comments