题解 | 彩色宝石项链

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int solve(string s) {
    int n = s.length();
    // 处理首尾相接
    s = s + s;
    
    // 记录需要的宝石
    unordered_map<char, int> need = {
        {'A', 1}, {'B', 1}, {'C', 1}, {'D', 1}, {'E', 1}
    };
    int needCount = 5;  // 需要的不同宝石数
    
    // 滑动窗口
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int valid = 0;  // 已找到的不同宝石数
    int minLen = s.length() + 1;  // 最短子串长度
    
    while(right < s.length()) {
        char c = s[right];
        right++;
        
        // 更新窗口数据
        if(need.count(c)) {
            window[c]++;
            if(window[c] == 1) valid++;
        }
        
        // 尝试缩小窗口
        while(valid == needCount) {
            minLen = min(minLen, right - left);
            
            char d = s[left];
            left++;
            
            if(need.count(d)) {
                window[d]--;
                if(window[d] == 0) valid--;
            }
        }
    }
    
    // 如果找不到包含所有宝石的子串
    if(minLen > n) return 0;
    
    // 返回剩余宝石数量
    return n - minLen;
}

int main() {
    string s;
    while(cin >> s) {
        cout << solve(s) << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static int solve(String s) {
        int n = s.length();
        // 处理首尾相接
        s = s + s;
        
        // 记录需要的宝石
        Map<Character, Integer> need = new HashMap<>();
        for(char c : "ABCDE".toCharArray()) {
            need.put(c, 1);
        }
        int needCount = 5;
        
        // 滑动窗口
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int valid = 0;
        int minLen = s.length() + 1;
        
        while(right < s.length()) {
            char c = s.charAt(right);
            right++;
            
            // 更新窗口数据
            if(need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if(window.get(c) == 1) valid++;
            }
            
            // 尝试缩小窗口
            while(valid == needCount) {
                minLen = Math.min(minLen, right - left);
                
                char d = s.charAt(left);
                left++;
                
                if(need.containsKey(d)) {
                    window.put(d, window.get(d) - 1);
                    if(window.get(d) == 0) valid--;
                }
            }
        }
        
        // 如果找不到包含所有宝石的子串
        if(minLen > n) return 0;
        
        // 返回剩余宝石数量
        return n - minLen;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s = sc.next();
            System.out.println(solve(s));
        }
    }
}

def solve(s):
    n = len(s)
    # 处理首尾相接
    s = s + s
    
    # 记录需要的宝石
    need = {'A': 1, 'B': 1, 'C': 1, 'D': 1, 'E': 1}
    need_count = 5
    
    # 滑动窗口
    window = {}
    left = right = 0
    valid = 0
    min_len = len(s) + 1
    
    while right < len(s):
        c = s[right]
        right += 1
        
        # 更新窗口数据
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == 1:
                valid += 1
        
        # 尝试缩小窗口
        while valid == need_count:
            min_len = min(min_len, right - left)
            
            d = s[left]
            left += 1
            
            if d in need:
                window[d] -= 1
                if window[d] == 0:
                    valid -= 1
    
    # 如果找不到包含所有宝石的子串
    if min_len > n:
        return 0
    
    # 返回剩余宝石数量
    return n - min_len

if __name__ == "__main__":
    while True:
        try:
            s = input()
            print(solve(s))
        except:
            break