如何用Python/Java计算使字符串分组均匀所需添加的字符数

我曾受邀参加初级Java开发岗位的面试，前期一切顺利，直到技术面试环节——这是一场现场编程挑战，技术负责人全程观察我用Java解题。这件事发生在大约一年前，直到现在我仍不知道该如何解决这个问题。从那以后我开始学习Python，也曾尝试用Python解决，但依然毫无头绪。

编程挑战要求 #

基于用户输入的字符串，编写一个函数返回需要添加多少个字符才能让字符串的字符分组实现均匀分布。

示例说明 #

示例1：
输入为"abba"，该字符串包含3个分组：

• 第一组："a"
• 第二组："bb"
• 第三组："a"
  为了实现均匀平衡，我们需要：
• 在第一组添加1个"a"
• 第二组无需操作
• 第三组添加1个"a"
  处理后的字符串为"aabbaa"，函数返回值为"2"

示例2：
输入为"baaababba"，该字符串包含6个分组：

• 第一组："b"
• 第二组："aaa"
• 第三组："b"
• 第四组："a"
• 第五组："bb"
• 第六组："a"
  为实现均匀平衡，需进行如下操作：
• 第一组添加2个"b"
• 第二组无需操作
• 第三组添加2个"b"
• 第四组添加2个"a"
• 第五组添加1个"b"
• 第六组添加2个"a"
  处理后的字符串为"bbbaaabbbaaabbbaaa"，函数返回值为"9"

示例3：
输入为"aaaa"，该字符串仅含1个分组："aaaa"
无需添加任何字符，函数返回值为"0"

示例4：
输入为"aabbaabb"，该字符串包含4个分组：

• 第一组："aa"
• 第二组："bb"
• 第三组："aa"
• 第四组："bb"
  所有分组长度相同，无需添加字符，函数返回值为"0"

我尝试的Python代码 #

def string_evaluator(user_input):
    input_to_list = []
    list_to_dic = {}
    group_count = 1
    biggest_group = 1
    for i in user_input:
        input_to_list.append(i)
    for char in input_to_list:
        character = char[0]
        if character not in list_to_dic:
        list_to_dic[character] = []
        list_to_dic[character].append(char)

    # print(list_to_dic)

解决方案 #

Python实现 #

核心思路：

1. 把字符串拆分成连续相同字符的分组，记录每个分组的字符和长度
2. 找到所有分组中的最大长度（要让所有分组都达到这个长度才能实现均匀分布）
3. 累加每个分组当前长度与最大长度的差值，得到需要添加的总字符数

def calculate_additional_chars(s):
    if not s:
        return 0
    
    # 拆分字符串为连续字符分组
    groups = []
    current_char = s[0]
    current_length = 1
    
    for char in s[1:]:
        if char == current_char:
            current_length += 1
        else:
            groups.append((current_char, current_length))
            current_char = char
            current_length = 1
    # 添加最后一个分组
    groups.append((current_char, current_length))
    
    # 找出最大分组长度
    max_length = max(length for _, length in groups)
    
    # 计算总添加字符数
    total_add = 0
    for _, length in groups:
        total_add += max_length - length
    
    return total_add

# 测试示例
print(calculate_additional_chars("abba"))          # 输出2
print(calculate_additional_chars("baaababba"))    # 输出9
print(calculate_additional_chars("aaaa"))         # 输出0
print(calculate_additional_chars("aabbaabb"))     # 输出0

Java实现 #

思路与Python一致，步骤相同：

public class StringBalancer {
    public static int calculateAdditionalChars(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        
        // 第一次遍历，找出最大分组长度
        char currentChar = s.charAt(0);
        int currentLength = 1;
        int maxLength = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == currentChar) {
                currentLength++;
            } else {
                maxLength = Math.max(maxLength, currentLength);
                currentChar = s.charAt(i);
                currentLength = 1;
            }
        }
        maxLength = Math.max(maxLength, currentLength);
        
        // 第二次遍历，计算需要添加的总字符数
        int totalAdd = 0;
        currentChar = s.charAt(0);
        currentLength = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == currentChar) {
                currentLength++;
            } else {
                totalAdd += maxLength - currentLength;
                currentChar = s.charAt(i);
                currentLength = 1;
            }
        }
        totalAdd += maxLength - currentLength;
        
        return totalAdd;
    }
    
    public static void main(String[] args) {
        System.out.println(calculateAdditionalChars("abba"));          // 输出2
        System.out.println(calculateAdditionalChars("baaababba"));    // 输出9
        System.out.println(calculateAdditionalChars("aaaa"));         // 输出0
        System.out.println(calculateAdditionalChars("aabbaabb"));     // 输出0
    }
}

内容的提问来源于stack exchange，提问作者Gabriel Vieira