Question

1624. Largest Substring Between Two Equal Characters

中文文档

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

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

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;
  }
}

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;
  }
};

func maxLengthBetweenEqualCharacters(s string) int {
  d := make([]int, 26)
  for i := range d {
    d[i] = -1
  }
  ans := -1
  for i, c := range s {
    c -= 'a'
    if d[c] == -1 {
      d[c] = i
    } else {
      ans = max(ans, i-d[c]-1)
    }
  }
  return ans
}

function maxLengthBetweenEqualCharacters(s: string): number {
  const n = s.length;
  const pos = new Array(26).fill(-1);
  let res = -1;
  for (let i = 0; i < n; i++) {
    const j = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
    if (pos[j] === -1) {
      pos[j] = i;
    } else {
      res = Math.max(res, i - pos[j] - 1);
    }
  }
  return res;
}

impl Solution {
  pub fn max_length_between_equal_characters(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let mut pos = [-1; 26];
    let mut res = -1;
    for i in 0..n {
      let j = (s[i] - b'a') as usize;
      let i = i as i32;
      if pos[j] == -1 {
        pos[j] = i;
      } else {
        res = res.max(i - pos[j] - 1);
      }
    }
    res
  }
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxLengthBetweenEqualCharacters(char* s) {
  int pos[26];
  memset(pos, -1, sizeof(pos));
  int n = strlen(s);
  int res = -1;
  for (int i = 0; i < n; i++) {
    char c = s[i];
    int j = c - 'a';
    if (pos[j] == -1) {
      pos[j] = i;
    } else {
      res = max(res, i - pos[j] - 1);
    }
  }
  return res;
}