【Leetcode 每日一题】3138. 同位字符串连接的最小长度

问题背景

给你一个字符串 $s$，它由某个字符串 $t$ 和若干 $t$ 的 同位字符串 连接而成。
请你返回字符串 $t$ 的 最小 可能长度。
同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。

数据约束

• $1\le s.length\le 10^5$
• $s$ 只包含小写英文字母。

解题过程

可以将问题转换为，能否将给定的字符串拆分成若干个字符种类完全一致，且同种字符出现的次数也一样的子串。
这样一来拆分的时候显然只能根据字符串长度的因子来拆分，否则的话会出现子串长度都不一样的情况，一定是不符合条件的。
不要求输出不同的字串，那么可以用哈希表来比较各个字串。

实现的时候虽然形式上写出了三重循环，实际上最终的时间复杂度是 $O(NL)$ 这个水平，其中 $N$ 代表字符串长度的因子的数量，$L$ 代表字符串长度。由于题目所给的字符串长度不超过 $10^5$，$N$ 最大为 $128$，完全可以接受。

具体实现

class Solution {
    private static final int SIZE = 26;

    public int minAnagramLength(String s) {
        int[] map = new int[SIZE];
        char[] chS = s.toCharArray();
        int n = chS.length;
        for(int i = 1; i < n; i++) {
            // 非因子不作进一步处理
            if(n % i != 0) {
                continue;
            }
            if(check(chS, i)) {
                return i;
            }
        }
        return n;
    }

    private boolean check(char[] chS, int i) {
        int[] map = new int[SIZE]; // map 统计上一个子串中各个字符出现的次数
        for(int j = 0; j < chS.length; j += i) {
            int[] count = new int[SIZE]; // count 统计当前子串中各个字符出现的次数
            for(int k = j; k < j + i; k++) {
                count[chS[k] - 'a']++;
            }
            // 出现两个哈希表不一致的情形，可以直接判断这两个串不符合条件
            if(j > 0 && !Arrays.equals(map, count)) {
                return false;
            }
            // 交换数组引用，维护定义
            map = count;
        }
        return true;
    }
}

梳理总结

这里 灵神的题解 中用到了类似 $goto$ 的循环控制标记，实际上把判断的方法从主流程中抽离出去就可以避免这样的操作。
从中可以看出，抽方法除了可以实现代码复用之外，还可以起到简化语义的作用。