题目链接：

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

用字符间隔考虑。

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

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

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

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

答案就是min(dis1,dis2)。

---

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 #define inf (1LL << 30)  8  9 const int N = 100010;10 char str[N];11 int tmp[N];12 int arr[N];13 bool vis[30];14 15 int main(){16 17     ios::sync_with_stdio(false);18     cin.tie(0);19 20     cin >> str;21     int len = strlen(str) - 1;22     23     for(int i = 0; i <= len; i++){24         arr[i] = str[i] - 'a' + 1;25         vis[arr[i]] = true;  //哪些字符出现过26     }27     28 29     int dis1 = inf;30     int dis2 = inf;31     int l = 0;32     for(int o = 0; o < 30; o++){ //'a'~'z'33         if(!vis[o]) continue;34 35         l = 0;36         for(int i = 0; i <= len; i++){37             if(o == arr[i]) tmp[l++] = i;38         }39         --l;40         //出现一次的41         if(l == 0){42             int v = 0;43             v = max(v,max(tmp[l] - 0 + 1,len - tmp[0] + 1));44             dis1 = min(dis1,v);45         }46         //出现多次的47         else{48             int v = 0;49             for(int i = 1; i <= l; i++){50                 v = max(v,tmp[i] - tmp[i - 1]);51             }52 53 54             v = max(v,tmp[0] - 0 + 1); //与字符串开头55             v = max(v,len - tmp[l] + 1);//与字符串结尾56 57             dis2 = min(dis2,v);58         }  59     }60 61 62     cout << min(dis1,dis2) << endl;63 64     getchar();getchar();65 66     return 0;67 }