顺序遍历，定长列表，哈希映射两种数据结构，求解《1624. 两个相同字符之间的最长子字符串》
例题
1624. 两个相同字符之间的最长子字符串
给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。
子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：s = "aa"
输出：0
解释：最优的子字符串是两个 'a' 之间的空子字符串。
示例 2：
输入：s = "abca"
输出：2
解释：最优的子字符串是 "bc" 。
示例 3：
输入：s = "cbzxy"
输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。
示例 4：
输入：s = "cabbac"
输出：4
解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
提示：
1 <= s.length <= 300
s 只含小写英文字母
答案
定长列表
var maxLengthBetweenEqualCharacters = function(s) {
const n = s.length, h = new Uint16Array(26)
let r = -1
for (let i = 0; i < n; i++) {
if (h[s.charCodeAt(i) - 97] === 0) h[s.charCodeAt(i) - 97] = i + 1
else r = Math.max(r, i - h[s.charCodeAt(i) - 97])
}
return r
};function maxLengthBetweenEqualCharacters(s: string): number {
const n = s.length, h = new Uint16Array(26)
let r = -1
for (let i = 0; i < n; i++) {
if (h[s.charCodeAt(i) - 97] === 0) h[s.charCodeAt(i) -97] = i + 1
else r = Math.max(r, i - h[s.charCodeAt(i) - 97])
}
return r
};class Solution {
function maxLengthBetweenEqualCharacters($s) {
$n = strlen($s);
$h = array_fill(0, 26, 0);
$r = -1;
for ($i = 0; $i < $n; $i++) {
if ($h[ord($s[$i]) - 97] === 0) $h[ord($s[$i]) - 97] = $i + 1;
else $r = max($r, $i - $h[ord($s[$i]) - 97]);
}
return $r;
}
}func maxLengthBetweenEqualCharacters(s string) int {
h, r := make([]int, 26), -1
for i, c := range s {
if h[c - 'a'] == 0 {
h[c - 'a'] = i + 1
} else {
r = max(r, i - h[c - 'a'])
}
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int maxLengthBetweenEqualCharacters(String s) {
int n = s.length(), r = -1;
int[] h = new int[26];
for (int i = 0; i < n; i++) {
if (h[s.charAt(i) - 'a'] == 0) h[s.charAt(i) - 'a'] = i + 1;
else r = Math.max(r, i - h[s.charAt(i) - 'a']);
}
return r;
}
}public class Solution {
public int MaxLengthBetweenEqualCharacters(string s) {
int n = s.Length, r = -1;
int[] h = new int[26];
for (int i = 0; i < n; i++) {
if (h[s[i] - 'a'] == 0) h[s[i] - 'a'] = i + 1;
else r = Math.Max(r, i - h[s[i] - 'a']);
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
int maxLengthBetweenEqualCharacters(char * s){
int* h = malloc(sizeof(int) * 26);
memset(h, 0, sizeof(int) * 26);
int n = strlen(s), r = -1;
for (int i = 0; i < n; i++) {
if (h[s[i] - 'a'] == 0) {
h[s[i] - 'a'] = i + 1;
} else {
r = MAX(r, i - h[s[i] - 'a']);
}
}
return r;
}class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
int n = s.size(), r = -1;
vector<int> h(26, 0);
for (int i = 0; i < n; i++) {
if (h[s[i] - 'a'] == 0) h[s[i] - 'a'] = i + 1;
else r = max(r, i - h[s[i] - 'a']);
}
return r;
}
};class Solution:
def maxLengthBetweenEqualCharacters(self, s: str) -> int:
h, r = [0] * 26, -1
for i, c in enumerate(s):
if h[ord(c) - 97] == 0: h[ord(c) - 97] = i + 1
else: r = max(r, i - h[ord(c) - 97])
return r哈希映射 · 字典
var maxLengthBetweenEqualCharacters = function(s) {
const n = s.length, h = new Map
let r = -1
for (let i = 0; i < n; i++) {
if (h.has(s.charCodeAt(i)) === false) h.set(s.charCodeAt(i), i + 1)
else r = Math.max(r, i - h.get(s.charCodeAt(i)))
}
return r
};var maxLengthBetweenEqualCharacters = function(s) {
const n = s.length, h = Object.create(null)
let r = -1
for (let i = 0; i < n; i++) {
if (h[s.charCodeAt(i)] === void 0) h[s.charCodeAt(i)] = i + 1
else r = Math.max(r, i - h[s.charCodeAt(i)])
}
return r
};function maxLengthBetweenEqualCharacters(s: string): number {
const n = s.length, h = new Map
let r = -1
for (let i = 0; i < n; i++) {
if (h.has(s.charCodeAt(i) - 97) === false) h.set(s.charCodeAt(i) - 97, i + 1)
else r = Math.max(r, i - h.get(s.charCodeAt(i) - 97))
}
return r
};class Solution {
function maxLengthBetweenEqualCharacters($s) {
$n = strlen($s);
$h = array();
$r = -1;
for ($i = 0; $i < $n; $i++) {
if ($h[ord($s[$i]) - 97] === null) $h[ord($s[$i]) - 97] = $i + 1;
else $r = max($r, $i - $h[ord($s[$i]) - 97]);
}
return $r;
}
}func maxLengthBetweenEqualCharacters(s string) int {
h, r := map[rune]int{}, -1
for i, c := range s {
if h[c - 'a'] == 0 {
h[c - 'a'] = i + 1
} else {
r = max(r, i - h[c - 'a'])
}
}
return r
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int maxLengthBetweenEqualCharacters(String s) {
int n = s.length(), r = -1;
Map<Integer, Integer> h = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
if (h.containsKey(s.charAt(i) - 'a') == false) h.put(s.charAt(i) - 'a', i + 1);
else r = Math.max(r, i - h.get(s.charAt(i) - 'a'));
}
return r;
}
}public class Solution {
public int MaxLengthBetweenEqualCharacters(string s) {
int n = s.Length, r = -1;
Dictionary<int, int> h = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (h.ContainsKey(s[i] - 'a') == false) h.Add(s[i] - 'a', i + 1);
else r = Math.Max(r, i - h[s[i] - 'a']);
}
return r;
}
}#define MAX(a, b) (a > b ? a : b)
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
int maxLengthBetweenEqualCharacters(char * s){
HashItem* h = NULL;
int n = strlen(s), r = -1;
for (int i = 0; i < n; i++) {
HashItem* pEntry = NULL;
int t = s[i] - 'a';
HASH_FIND_INT(h, &t, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = t;
pEntry->val = i + 1;
HASH_ADD_INT(h, key, pEntry);
} else {
r = MAX(r, i - pEntry->val);
}
}
HashItem* cur, *tmp;
HASH_ITER(hh, h, cur, tmp) {
free(cur);
}
return r;
}class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
int n = s.size(), r = -1;
unordered_map<int, int> h;
for (int i = 0; i < n; i++) {
if (h[s[i] - 'a'] == 0) h[s[i] - 'a'] = i + 1;
else r = max(r, i - h[s[i] - 'a']);
}
return r;
}
};class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
int n = s.size(), r = -1;
unordered_map<int, int> h;
for (int i = 0; i < n; i++) {
if (h.find(s[i] - 'a') == h.end()) h.emplace(s[i] - 'a', i + 1);
else r = max(r, i - h[s[i] - 'a']);
}
return r;
}
};class Solution:
def maxLengthBetweenEqualCharacters(self, s: str) -> int:
h, r = dict(), -1
for i, c in enumerate(s):
if ord(c) - 97 not in h: h[ord(c) - 97] = i + 1
else: r = max(r, i - h[ord(c) - 97])
return r