彩色宝石项链

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
int main(){
	string s;
	int i,j,num,len;
	while(cin>>s){
		len=s.length();
		s=s+s; 
		i=0,j=0,num=0;
		int Min=len;
		map<char,int> book;
		while(true){
			while(i<s.length()&&num<5){
				if((s[i]=='A'||s[i]=='B'||s[i]=='C'||s[i]=='D'||s[i]=='E')
					&&book[s[i]]++==0)
					num++;
				i++;
			}
			if(num<5) break;
			Min=min(Min,i-j);
			if((s[j]=='A'||s[j]=='B'||s[j]=='C'||s[j]=='D'||s[j]=='E')
				&&--book[s[j]]==0) num--;
			j++;
		}
		printf("%d\n",len-Min);
	}
}//尺取法，求包含ABCDE的最短字串

#include<iostream>
#include<string>
#include<vector>
using namespace std;
//判断str从start开始长度为length的子串中是否包括了ABCDE
bool isPerfect(string str, int start, int length)
{
    vector<bool> vec(5, false);//5个bool标记ABCDE是否找到
    for(int i = 0; i < length; i++)
    {
        int index = str[start + i] - 'A';
        if(index < 5)
            vec[index] = true;
    }
    return vec[0] && vec[1] && vec[2] && vec[3] && vec[4];
}
int main()
{
    string str;
    while(cin >> str)
    {
        bool find = false;
        int n = str.size();
        if(n <= 5)
        {
            cout << 0 << endl;
            continue;
        }
            
        str = str + str;//省去环处理
        for(int length = 5; length <= n; length++)//长度
        {
            for(int i = 0; i < n; i++)//起点
            {
                if(isPerfect(str, i, length))
                {
                    cout <<  n - length << endl;
                    find = true;
                    break;
                }
            }
            if(find)
                break;
        }
    }
}

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println(gem(sc.nextLine()));
		sc.close();
	}

	public static int gem(String str) {
		char[] ca = str.toCharArray();
		int len = str.length();
		for (int x = 5; x < len; x++) { // x为截取宝石的个数
			for (int y = 0; y < len; y++) {//y为x确定的情况下迭代的次数
				StringBuilder temp = new StringBuilder("");
				for (int z = y; z < y + x; z++) {
					temp.append(ca[z % len]);
				}
				String t = temp.toString();
				if (t.contains("A") && t.contains("B") && t.contains("C") && t.contains("D") && t.contains("E")) {
					return len - x;
				}
			}
		}
		return 0;
	}
}

O(n^2)的暴力 从第一个开始 找出ABCDE或者长度超过了给的长度为止 更新最大剩余珠宝量

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int ha[5], ans;
int main(){
    string a;
    while(cin>>a){
        ans = 0;
        int len = a.length();
        for(int i = 0; i < len; i++){
            if(a[i] < 'A' || a[i] > 'E') continue;
            memset(ha, 0, sizeof(ha));
            int cnt = 1, j = (i + 1) % len, num = 1;
            ha[int(a[i])-65] = 1;
            while(cnt <= len){
                cnt++;
                if(a[j] >= 'A' && a[j] <= 'E' && ha[int(a[j])-65] == 0) {    
                    ha[int(a[j])-65] = 1; 
                    num++;
                    if(num == 5) {ans = max(ans, len-cnt); break;}
                }
                j = (j + 1) % len;
            }
        }
        printf("%d\n", ans);
    }
}

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

int main()
{
	string str;
	while (cin>>str)
	{
		int len = str.length();
		for (int i = 0; i < len; i++)
		  {
			str.push_back(str[i]);
		  }
		int min =len;
		for (int i = 0; i <= len+5; i++)
		{
			int flag= 0x0000;
			int temp= 0;
			int j = i;
			while ((j <=len + 5 )&& (flag!= 0x1f))
			{
				if (str[j] >= 'A'&&str[j] <= 'E')
				{
					flag|=1<<(str[j]-'A');
				}
				j++;
				temp++;
				if (flag == 0x1f)
					break;
			}
			if (temp < min&& 0x1f ==flag)
				min = temp;
		}
		cout << len - min << endl;
	}
}

来解释一下思路，
此题本质上是在一个字符串中找出包含ABCDE的最小长度的子字符串，学者最后能拿到的宝石的数目就是 字符串的长度减去最小字符串的长度。

那么为了找出最短的字符串，我们可以用枚举发来找出所有可能包含的字符串：
1.首先子字符串要至少包含ABCDE五个宝石，那么子字符串的可能长度区间就是 5 至 字符串的总长度

1. 遍历每一个长度区间，对于给定字符串，我们从每一位开始 分别截取对于的对应长度区间的字符串为子字符串，然后对每一个子字符串判断是否全部包含ABCDE这五个宝石，
   一旦包含，那么这个子字符串就是我们要找的长度最短的字符串。这里解释一下为什么这个子字符串是长度最小的， 因为我们是对长度区间进行遍历，所有 程序会依次列举所有长度为5的子字符串，长度为6的子字符串 知道长度为字符串本身的子字符串，长度依次递增，所以一旦找到符合的子字符串，那么这个字符串长度必然为最短。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            System.out.println(handle(sc.nextLine()));
        }
    }

    public static int handle(String string){
        //最大包含所有宝石的子字符串长度范围 5 - string.length
        //子字符串的长度依次递增
        char[] chars=string.toCharArray();
        for(int i=5;i<=chars.length;i++){
            //从字符串每一位为起点，开始依次截取对应范围长度的所有子字符串
            for(int j=0;j<string.length();j++){
                //保存每一个截取完的字符串
                StringBuffer buf=new StringBuffer();
                for(int k=j;k<j+i;k++){
                    //k 为截取的索引，注意数组越界
                         buf.append(chars[k%string.length()]);
                }
                //验证截取的字符串是否包含所有的宝石，一旦包含，
                //此字符串为最小长度
                String subString=buf.toString();
                if(subString.contains("A")
                  && subString.contains("B")
                  && subString.contains("C")
                  && subString.contains("D")
                  && subString.contains("E")){
                          return chars.length-subString.length();
                  }                  
            }
        }
        // 没有找到包含的子字符串
        return 0;
    }
}

用一个整数表示某字符串所包含的宝石种类，第0bit为1，表示存在红宝石；第1bit为1，表示存在蓝宝石……以此类推。当两个字符合并的时候，只需要将两个整数按位取或，就能表示合并后存在的宝石种类。

#include<bits/stdc++.h>

using namespace std;

char dict(char c){
    switch(c){
        case 'A': return 1;
        case 'B': return 0b10;
        case 'C': return 0b100;
        case 'D': return 0b1000;
        case 'E': return 0b10000;
        default: return 0;
    }
}

int diamonds(string s){
    int n=s.size();
    int dp[n][n];//从dp[i][j]表示从i开始，长为j+1的串包含多少种宝石
    for(int i=0;i<n;i++){
        dp[i][0]=dict(s[i]);
    }
    for(int j=1;j<n;j++){
        for(int i=0;i<n;i++){
            dp[i][j]=dp[i][j-1]|dp[(i+j)%n][0];
            if(dp[i][j]>=0b11111){
                return n-j-1; 
            }
        }
    }
    return 0;
}

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

# include <stdio.h>
# include <string.h>
int main(){
    char s[10000];
    int n,len,loc,i,j;
    while(scanf("%s",s)!=EOF){
        n = len = strlen(s);//n为项链长度，len为满足条件的一截珠宝的长度 
        for(i=0;i<n;++i){           
            if(s[i]<'F'){//从所选5种珠宝开始
                int c[5]={0};//用c统计五种珠宝遇到的次数 
                for(j=0;j<len;++j){
                    loc=(i+j)%n;//使首尾相接 
                    switch(s[loc]){
                        case 'A':c[0]++;break;
                        case 'B':c[1]++;break;
                        case 'C':c[2]++;break;
                        case 'D':c[3]++;break;
                        case 'E':c[4]++;break;
                    }
                    if(c[0]&&c[1]&&c[2]&&c[3]&&c[4])break;//5种珠宝同时出现,退出循环
                }
                if(j+1<len)len=j+1;
            }
            if(len==5)break;//若五种珠宝相连，则退出循环 
        }
        printf("%d\n",n-len);
    }
    return 0;
}

import java.util.Scanner;

public class FindSequence {
    
    public static void main(String[] argv) {
        Scanner sin = new Scanner(System.in);
        while(sin.hasNext()){
            String s = sin.nextLine();
            char[] c = s.toCharArray();
            int length = c.length;
            int flag =0,max=0;
            int i,j,k;
            for(i=0;i<length;i++){
                flag =0;
                for(j=i;j-i<length;j++){
                    if(c[j%length] == 'A'||c[j%length] == 'B'||c[j%length] == 'C'
                            ||c[j%length] == 'D'||c[j%length] == 'E' ){
                        flag |= 1<< c[j%length]-'A'; 
                        if(flag == 31){
                            max =Math.max(max, length-j+i-1);
                            break;
                        }
                    }

                }
            }
            System.out.printf("%d\n",max);
        }
    }
}

	

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int main() {
    int typeOfStone = 0, minlen = -1;
    int numOfStone[6] = {0};
    string str;
    queue<int> que;

    cin >> str;
    str += str;

    for (int i = 0; i < str.size(); i++) {
        if (str[i] - 'A' < 5) {
            int p = str[i] - 'A';

            if (numOfStone[p] == 0) typeOfStone++;

            numOfStone[p]++;
            que.push(i);

            if (typeOfStone >= 5) {

                while(numOfStone[str[que.front()] - 'A'] > 1) {
                    numOfStone[str[que.front()] - 'A']--;
                    que.pop();
                }

                if (minlen == -1 || minlen > (i + 1 - que.front())) {
                    minlen = i + 1 - que.front();
                } 
            }
        }
    }

    if (typeOfStone < 5) {
        cout << 0 << endl;
    } else {
        cout << (str.size()/2) - minlen << endl;
    }

}

自己怎么测都没错 到这怎么就错了呢？？？
望各位大佬指点

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String str = "ABCDE";
        char[] ch = str.toCharArray();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            int len = 0;
            int maxSize = 0;
            //判断字符串中是否全部包含ABCDE 不包含直接输出0
            if (haveABCDE(s, str) == false) {
                System.out.println(maxSize);
                
            } else {
                //处理字符串 OPABCDEF 变成 OPABCDEFOPA 方便计算最多拿到宝石数量 （环）
                s = changeStr(s, ch);
                for (int i = 0; i < s.length(); i++) {
                    //ifLike方法判断字符串哪一位 是ABCDE 中的
                    if (ifLike(s.charAt(i), ch) == false) {
                        len++;
                    } else {
                        if (maxSize <= len) {
                            maxSize = len;
                        }
                        len = 0;
                    }
                }
                System.out.println(maxSize);
            }
        }
    }
    public static String changeStr(String s, char[] ch) {
        int c = 0;
        for (int i = 0; i < ch.length; i++) {
            if (ifLike(s.charAt(i), ch) == true) {
                c = i;
                break;
            }
        }
        s = s + s.substring(0, c + 1);
        return s;
    }
    public static boolean ifLike(char c, char[] ch) {
        for (int i = 0; i < ch.length; i++) {
            if (c == ch[i])
                return true;
        }
        return false;
    }
    public static boolean haveABCDE(String s, String s1) {
        for (int i = 0; i < s1.length(); i++) {
            if (s.contains(s1.substring(i, i + 1)) == false) {
                return false;
            }
        }
        return true;
    }
}

分享一个简单粗暴的思路和解答。
1.将每次输入的数组直接乘2拼接起来（NN=N+N），然后每次初始化的判断区间是输入数组的长度(N),之后每次左边收一格（left+=1）,发现不能收了之后开始收右边（right-=1）
2.两边都不能收的时候返回此时剩余的宝石（len(N)-(r-l)），存入数组，循环输入字符串长度的次数
3.打印存入每次循环的值中的最大值即可

import sys
N=input()
NN=N+N
res=[]
for i in range(0,len(N)):
    l=i;r=i+len(N)-1
    left=0;right=0
    while((left==0)|(right==0)):
        while(('A'in NN[l:r])&('B'in NN[l:r])&('C'in NN[l:r])&('D'in NN[l:r])&('E'in NN[l:r])):
            l+=1
        left=1
        l-=1
        while(('A'in NN[l:r])&('B'in NN[l:r])&('C'in NN[l:r])&('D'in NN[l:r])&('E'in NN[l:r])):
            r-=1
        right=1
        r+=1
    res+=[len(N)-(r-l)]
print(max(res))

目标：找到最短的包含ABCDE的substring，总长度减去substring长度即为答案
思路：
1. 将字符串重复两次构成一个新字符串db
2. 左右两根指针，保持一个窗口
3. 每次移动左右指针后，检查l - r中间字符串是否包含ABCDE：
a. 如果不包含全部，r++
b. 如果全包含全部，l++，同时判断是否需要更新最小长度

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

int main() {
    string s;
    while (cin >> s) {
        string db = s + s;
        int n = db.size();
        int l = 0, r = 0, minLen = INT_MAX;
        vector<int> check(5, 0);
        if (db[0] >= 'A' && db[0] <= 'E') {
            check[db[0] - 'A']++;
        }
        while (r < n) {
            bool flag = true;
            for (int num : check) {
                if (num == 0) {
                    flag = false;
                }
            }
            if (flag) {
                minLen = min(minLen, r - l + 1);
                int ind = db[l] - 'A';
                if (ind >= 0 && ind <= 4) {
                    check[ind]--;
                }
                l++;
            }
            else {
                r++;
                if (r < n) {
                    int ind = db[r] - 'A';
                    if (ind >= 0 && ind <= 4) {
                        check[ind]++;
                    }
                }
            }
        }
        if (minLen == INT_MAX || minLen > int(s.size())) {
            cout << 0 << endl;
        }
        else {
            cout << int(s.si***Len << endl;
        }
        system("PAUSE");
    }
}

/*
小学生代码233，让str=str+str就可以看成圈了，然后找出含ABCDE最短的
长度(len+1),然后用str的总长去减他再除二就是剩下的宝石数
*/
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

bool if_in_(char x, char wh[])
{
    for (int i = 0; i < 5; i++)
    {
        if (wh[i] == x) return true;
    }
    return false;
}

int is_finished(map<char, int> js)
{
    if (js['A'] == 1 && js['B'] == 1 && js['C'] == 1 && js['E'] == 1 && js['D'] == 1) return 1;
    return 0;
}

int main()
{
    char wh[] = { 'A', 'B', 'C', 'D', 'E'};
    map<char, int> js;
    vector<int> len_sz;
    js['A'] = 0;
    js['B'] = 0;
    js['C'] = 0;
    js['D'] = 0;
    js['E'] = 0;
    string str;
    cin >> str;
    str += str;

    

    int num = 0;
    
    for (int i = 0; i < str.size(); i++)
    {
        if (if_in_(str[i], wh))
        {
            for (int j = i; j < str.size(); j++)
            {
                if (if_in_(str[j], wh))
                {
                    js[str[j]] = 1;
                    if (is_finished(js))
                    {
                        len_sz.push_back(j - i);
                        js['A'] = 0;
                        js['B'] = 0;
                        js['C'] = 0;
                        js['D'] = 0;
                        js['E'] = 0;
                        break;
                    }
                }
            }
        }
    }
    
    int len = str.size();

    for (auto v : len_sz)
    {
        if (v < len)
        {
            len = v;
        }
    }

    cout << (str.size() - 2*(len+1)) / 2;

    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
 
using namespace std;

int main()
{     string s;     while(cin>>s)     {         int l = s.length();         int left=0, right=0, cnt=0, Min=l;         map<char, int> M;         s = s + s;         while(1)         {             while(right<s.length() && cnt<5)             {                 if(s[right]>='A' && s[right]<='E' && M[s[right]]++==0)                     cnt++;                 right++;             }             if(cnt<5)                 break;             Min = min(Min, right-left);             if(s[left]>='A' && s[left]<='E' && --M[s[left]]==0)                 cnt--;             left++;         }         cout<<l-Min<<endl;     }     return 0;
}