最短包含字符串的长度

链接
来源:牛客网

给定字符串str1和str2,求str1的字串中含有str2所有字符的最小字符串长度。

import java.util.Scanner;

public class Main {

    private static int solve(String str1, String str2) {

        int[] count = new int[256];

        for (int i = 0; i < str2.length(); ++i) {
            count[str2.charAt(i)]++;
        }

        int l = 0, r = 0, need = str2.length(), ret = Integer.MAX_VALUE;

        while (r < str1.length()) {
            count[str1.charAt(r)]--;
            if (count[str1.charAt(r)] >= 0) {
                need--;
            }
            if (need == 0) {
                while (count[str1.charAt(l)] < 0) {
                    count[str1.charAt(l++)]++;
                }
                ret = Math.min(ret, r - l + 1);
                count[str1.charAt(l++)]++;
                need++;
            }
            r++;
        }

        return ret == Integer.MAX_VALUE ? 0 : ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(solve(in.next(), in.next()));
        }
    }
}
上一篇:最长公共子串


下一篇:Files的常用方法有哪些