连续字母长度

题目描述

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

输入描述

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

输出描述

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

示例1

输入:

AAAAHHHBBCDHHHH
3

输出:

2

说明:

• 同一字母连续出现的最多的是A和H, 四次
• 第二多的是H, 3次, 但是H已经存在4个连续的, 故不考虑
• 下个最长子串是BB, 所以最终答案应该输出2

示例2

输入:

AABAAA
2

输出:

1

说明:

• 同一字母连续出现的最多的是A, 三次
• 第二多的还是A, 两次, 但A已经存在最大连续次数三次, 故不考虑
• 下个最长子串是B, 所以输出1

示例3

输入:

ABC
4

输出:

-1

示例4

输入:

ABC
2

输出:

1

题解

Python

import sys

def main():
    string = input().strip()
    k = int(input().strip())

    # 先遍历字符串, 分隔出连续相同字符, 然后统计其个数, 存放到计数字典中
    current_char = 'A'
    current_char_count = 0
    char_dict = dict()
    string_len = len(string)
    for char in string:
        # 如果当前的字符与上个字符不相同
        if current_char != char:
            # 保存到字典中
            if current_char_count > 0:
                # 如果该字符在字典中已经存在, 则只保存最大连续数
                last_count = char_dict.get(current_char)
                if last_count:
                    char_dict[current_char] = max(last_count, current_char_count)
                else:
                    char_dict[current_char] = current_char_count
            # 重置上个字符及其计数
            current_char = char
            current_char_count = 1
        else:
            current_char_count += 1

    # 处理最后一个字符
    if current_char_count > 0:
        # 如果该字符在字典中已经存在, 则只保存最大连续数
        last_count = char_dict.get(current_char)
        if last_count:
            char_dict[current_char] = max(last_count, current_char_count)
        else:
            char_dict[current_char] = current_char_count

    # 将字典转换成列表
    word_list = []
    for (char, count) in char_dict.items():
        word_list.append((count, char))
    # 基于最大连续数进行排序, 从高到低
    word_list.sort(key = lambda pair: pair[0], reverse = True)
    #print(word_list)

    # 并找到第 k 个字符, 注意下标从0开始计数, 而k是从1开始的
    if k <= len(word_list):
        print(word_list[k - 1][0])
    else:
        print(-1)

if __name__ == "__main__":
    main()

Rust

use std::cmp::Reverse;
use std::collections::HashMap;
use std::io::{stdin, BufRead};

fn main() {
    // 读取输入
    let mut s = String::new();
    let ret = stdin().lock().read_line(&mut s);
    assert!(ret.is_ok());
    let mut k_str = String::new();
    let ret = stdin().lock().read_line(&mut k_str);
    assert!(ret.is_ok());
    let k: usize = k_str.trim().parse().unwrap();

    // 先遍历字符串, 分隔出连续相同字符, 然后统计其个数, 存放到计数字典中
    let mut current_char: char = 'A';
    let mut current_char_count: usize = 0;
    let mut char_dict: HashMap<char, usize> = HashMap::new();
    for chr in s.trim().chars() {
        // 如果当前的字符与上个字符不相同
        if current_char != chr {
            // 保存到字典中
            if current_char_count > 0 {
                // 如果该字符在字典中已经存在, 则只保存最大连续数
                if let Some(last_count) = char_dict.get_mut(&current_char) {
                    *last_count = current_char_count.max(*last_count);
                } else {
                    char_dict.insert(current_char, current_char_count);
                }
            }

            // 重置上个字符及其计数
            current_char = chr;
            current_char_count = 1;
        } else {
            current_char_count += 1;
        }
    }

    // 处理最后一个字符
    if current_char_count > 0 {
        // 如果该字符在字典中已经存在, 则只保存最大连续数
        if let Some(last_count) = char_dict.get_mut(&current_char) {
            *last_count = current_char_count.max(*last_count);
        } else {
            char_dict.insert(current_char, current_char_count);
        }
    }

    // 将字典转换成列表
    let mut word_list: Vec<(char, usize)> = char_dict.into_iter().collect();
    // 基于最大连续数进行排序, 从高到低
    word_list.sort_by_key(|pair| Reverse(pair.1));
    //println!("{word_list:?}");

    // 并找到第 k 个字符, 注意下标从0开始计数, 而k是从1开始的
    if k <= word_list.len() {
        println!("{}", word_list[k - 1].1);
    } else {
        println!("-1");
    }
}

C++

#include <cassert>

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
  // 读取输入
  std::string s;
  std::getline(std::cin, s);
  int k = 0;
  std::cin >> k;

  // 先遍历字符串, 分隔出连续相同字符, 然后统计其个数, 存放到计数字典中
  char current_char = 'A';
  int current_char_count = 0;
  std::unordered_map<char, int> char_dict;
  for (char chr : s) {
    // 如果当前的字符与上个字符不相同
    if (current_char != chr) {
      // 保存到字典中
      if (current_char_count > 0) {
        // 如果该字符在字典中已经存在, 则只保存最大连续数
        auto iter = char_dict.find(current_char);
        if (iter != char_dict.end()) {
          iter->second = std::max(iter->second, current_char_count);
        } else {
          char_dict.emplace(current_char, current_char_count);
        }
      }

      // 重置上个字符及其计数
      current_char = chr;
      current_char_count = 1;
    } else {
      current_char_count += 1;
    }
  }

  // 处理最后一个字符
  if (current_char_count > 0) {
    // 如果该字符在字典中已经存在, 则只保存最大连续数
    auto iter = char_dict.find(current_char);
    if (iter != char_dict.end()) {
      iter->second = std::max(iter->second, current_char_count);
    } else {
      char_dict.emplace(current_char, current_char_count);
    }
  }

  // 将字典转换成列表
  std::vector<std::tuple<int, char>> word_list;
  for (const auto tuple : char_dict) {
    word_list.emplace_back(std::get<1>(tuple), std::get<0>(tuple));
  }
  // 基于最大连续数进行排序, 从高到低
  std::sort(word_list.begin(), word_list.end(),
      [](const std::tuple<int, char>& a, const std::tuple<int, char>& b) {
        return std::get<0>(a) > std::get<0>(b);
  });
  //for (const auto& item : word_list) {
  //  std::cout << std::get<1>(item) << ":" << std::get<0>(item) << std::endl;
  //}

  // 并找到第 k 个字符, 注意下标从0开始计数, 而k是从1开始的
  if (k <= word_list.size()) {
    std::cout << std::get<0>(word_list[k - 1]) << std::endl;
  } else {
    std::cout << "-1" << std::endl;
  }

  return 0;
}