(C卷,100分)- 连续字母长度（Java & JS & Python）

题目描述

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。

输入描述

第一行有一个子串(1<长度<=100)，只包含大写字母。

第二行为 k的值

输出描述

输出连续出现次数第k多的字母的次数。

用例

题目解析

本题第一个用例感觉也有歧义。

用例1，要求“AAAAHHHBBCDHHHH”中  重复度第3大的子串。其中：

• 重复度第1大子串是：AAAA和HHHH
• 重复度第2大子串是：HHH，由于字母H已经有了更大的重复度，因此HHH子串不计入比较

接下来是，实际上的第3大，名义上的第2大子串：BB

而用例1输出的第k=3大重复度的子串的长度是2，那就肯定是指BB子串。即要求“实际”第k大？而不是“名义”第k大？

但是用例2，要求“AABAAA”中，重复度第2大的子串。其中：

• 重复度第1大子串是：AAA
• 重复度第2大子串是：AA，由于字母A已经有了更大的重复度，因此HHH子串不计入比较

接下来是，实际上的第3大，名义上的第2大子串：B

而用例1输出的第k=2大重复度的子串的长度是1，这里又是取名义上第k大了？

或者本题还有另一种思路，那就是第k大，就是单纯按重复度降序后的第k个。

比如用例1： A:4，H:4，B:2，C:1，D:1

这里第k=3大，那就是B，子串长度为2

比如用例2：A:3，B:1

这里第k=2大，那就是B，子串长度为1

下面代码就是按照这个思路实现的。

2023.06.19

增加处理下 k <= 0的情况，此时直接返回-1

Java算法源码

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int k = sc.nextInt();
    System.out.println(getResult(s, k));
  }

  public static int getResult(String s, int k) {
    if (k <= 0) return -1;

    s += "0";

    HashMap<Character, Integer> count = new HashMap<>();

    char b = s.charAt(0);
    int len = 1;

    for (int i = 1; i < s.length(); i++) {
      char c = s.charAt(i);

      if (b == c) {
        len++;
      } else {
        if (!count.containsKey(b) || count.get(b) < len) {
          count.put(b, len);
        }
        len = 1;
        b = c;
      }
    }

    Integer[] arr = count.values().toArray(new Integer[0]);

    if (k > arr.length) return -1;
    else {
      Arrays.sort(arr, (x, y) -> y - x);
      return arr[k - 1];
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const { count } = require("console");
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    console.log(getResult(lines[0], lines[1]));
    lines.length = 0;
  }
});

/* 算法逻辑 */
function getResult(s, k) {
  if (k <= 0) return -1;

  s += "0";

  let count = {};

  let b = s[0];
  let len = 1;

  for (let i = 1; i < s.length; i++) {
    const c = s[i];

    if (b == c) {
      len++;
    } else {
      if (count[b] == undefined || count[b] < len) {
        count[b] = len;
      }
      len = 1;
      b = c;
    }
  }

  const arr = Object.values(count);

  if (k > arr.length) {
    return -1;
  } else {
    arr.sort((a, b) => b - a);
    return arr[k - 1];
  }
}

Python算法源码

# 输入获取
s = input()
k = int(input())


# 算法入口
def getResult():
    global s
    global k

    if k <= 0:
        return -1

    s += "0"

    count = {}

    b = s[0]
    long = 1

    for i in range(1, len(s)):
        c = s[i]

        if b == c:
            long += 1
        else:
            if count.get(b) is None or count[b] < long:
                count[b] = long
            long = 1
            b = c

    arr = list(count.values())

    if k > len(arr):
        return -1
    else:
        arr.sort(reverse=True)
        return arr[k - 1]


# 算法调用
print(getResult())