K-Dominant Character CodeForces

 

题目链接：https://vjudge.net/problem/CodeForces-888C

划一条线，使得不论怎么划线，都会出现一个特定的字符，那么这条线最短要多长。

用字符间隔考虑。

先判断哪些字符出现了，然后统计每个不同字符的出现次数，出现一次的和出现多次的分开判断。

出现一次的找到它的位置，取max(当前位置 - 字符串开始位置 + 1，字符串末位位置 - 当前位置 + 1)，

然后遍历所有出现一次的字符，得出max的最小值，并记录，dis1

出现多次的找到相邻两个相同字符的间隔，取最大间隔的间隔k，再得出第一个出现的相同字符和开头的间隔+1，最后一个出现的相同字符和字符串末尾的间隔+1，和k比较取最大dis2

答案就是min(dis1,dis2)。

---

 

#include <cstring>
#include <iostream>
#include <cstdio>

using namespace std;

#define inf (1LL << 30) 

const int N = 100010;
char str[N];
int tmp[N];
int arr[N];
bool vis[30];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> str;
    int len = strlen(str) - 1;
    
    for(int i = 0; i <= len; i++){
        arr[i] = str[i] - 'a' + 1;
        vis[arr[i]] = true;  //哪些字符出现过
    }
    

    int dis1 = inf;
    int dis2 = inf;
    int l = 0;
    for(int o = 0; o < 30; o++){ //'a'~'z'
        if(!vis[o]) continue;

        l = 0;
        for(int i = 0; i <= len; i++){
            if(o == arr[i]) tmp[l++] = i;
        }
        --l;
        //出现一次的
        if(l == 0){
            int v = 0;
            v = max(v,max(tmp[l] - 0 + 1,len - tmp[0] + 1));
            dis1 = min(dis1,v);
        }
        //出现多次的
        else{
            int v = 0;
            for(int i = 1; i <= l; i++){
                v = max(v,tmp[i] - tmp[i - 1]);
            }


            v = max(v,tmp[0] - 0 + 1); //与字符串开头
            v = max(v,len - tmp[l] + 1);//与字符串结尾

            dis2 = min(dis2,v);
        }  
    }


    cout << min(dis1,dis2) << endl;

    getchar();getchar();

    return 0;
}