395.至少有K个重复字符的最长子串

链接：395.至少有K个重复字符的最长子串
难度：Medium
标签：哈希表、字符串、分治、滑动窗口
简介：给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。

题解 1 - typescript

• 编辑时间：2021-07-29
• 执行用时：80ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：分割字符串分别统计。

function longestSubstring(s: string, k: number): number {
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const splits: number[] = [];
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]] < k) splits.push(i);
  }
  splits.push(s.length);
  if (splits.length === 1) return s.length;
  let pre = 0;
  let ans = 0;
  for (const p of splits) {
    const len = p - pre;
    if (len >= k) {
      ans = Math.max(ans, longestSubstring(s.substr(pre, len), k));
    }
    pre = p + 1;
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-02-27
• 执行用时：88ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：递归,分治。

function longestSubstring(s: string, k: number): number {
  const len = s.length;
  if (len === 0) return 0;
  if (len === 1) return +(k === 1);
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const regStr = Object.keys(map)
    .filter(key => map[key] < k)
    .join('|');
  if (regStr.length === 0) return s.length;
  const arr = s.split(new RegExp(regStr));
  return Math.max(...arr.map(str => longestSubstring(str, k)));
}

题解 3 - typescript

• 编辑时间：2021-02-27
• 执行用时：148ms
• 内存消耗：42.2MB
• 编程语言：typescript
• 解法介绍：读取可能值进行最长比较。

function longestSubstring(s: string, k: number): number {
  const len = s.length;
  if (len === 1) return +(k === 1);
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const set = new Set(
    Object.entries(map)
      .filter(([, v]) => v < k)
      .map(([k]) => k)
  );
  const runtimeMap = new Map<string, number>();
  const runtimeSet = new Set<string>();
  let ans = 0;
  for (let i = 0; i < len; i++) {
    const c = s[i];
    if (set.has(c)) continue;
    runtimeMap.clear();
    runtimeSet.clear();
    runtimeMap.set(c, 1);
    if (k > 1) runtimeSet.add(c);
    let lastIndex = i;
    while (++lastIndex < len) {
      const newChar = s[lastIndex];
      if (set.has(newChar)) break;
      const charCount = (runtimeMap.get(newChar) ?? 0) + 1;
      runtimeMap.set(newChar, charCount);
      charCount >= k ? runtimeSet.delete(newChar) : runtimeSet.add(newChar);
      if (runtimeSet.size === 0) ans = Math.max(ans, lastIndex - i + 1);
    }
  }
  return ans;
}

题解 4 - typescript

• 编辑时间：2021-02-27
• 执行用时：100ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：递归,分治。

function longestSubstring(s: string, k: number): number {
  const len = s.length;
  if (len === 0) return 0;
  if (len === 1) return +(k === 1);
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const regStr = Object.entries(map)
    .filter(([, v]) => v < k)
    .map(([k]) => k)
    .join('|');
  if (regStr.length === 0) return s.length;
  const arr = s.split(new RegExp(regStr));
  return Math.max(...arr.map(str => longestSubstring(str, k)));
}

题解 5 - typescript

• 编辑时间：2021-02-27
• 执行用时：88ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：递归,分治。

function longestSubstring(s: string, k: number): number {
  const len = s.length;
  if (len === 0) return 0;
  if (len === 1) return +(k === 1);
  const map: Record<string, number> = {};
  for (const c of s) map[c] = (map[c] ?? 0) + 1;
  const regStr = Object.keys(map)
    .filter(key => map[key] < k)
    .join('|');
  if (regStr.length === 0) return s.length;
  const arr = s.split(new RegExp(regStr));
  return Math.max(...arr.map(str => longestSubstring(str, k)));
}