本题是一道比较常见的双指针(或滑动窗口)题目
首先值得注意的是题目要求找到S的子串“恰好”包含2个h、1个i和1个o，不是“至少”包含。
本题的思路就是枚举子串的起点位置L=0, 1, 2, ... |S|-1， O(|S|)； 然后找到一个最短的，也就是右端点R最小的、使得S[L..R]“至少”包含2个h、1个i和1个o。
然后判断S[L..R]是不是“恰好”包含2个h、1个i和1个o；如果是，我们就找到了一个答案，就用R-L+1更新当前最短的答案。
本题可以用双指针(或滑动窗口)，奥妙就在于，当我们要枚举下一个起点L时，即令L=i变成L=i+1时，新的R(i+1)一定在R(i)的右边。
这样R不用从L+1开始计算，总的复杂度就是O(|S|)的了。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int res = solve(s);
System.out.println(res);
}
private static int solve(String s) { char a[] = s.toCharArray(); int j = 0; int len = Integer.MAX_VALUE; int begin = 0; int end = -1; for(int i = 0;i
if(j-i+1>=4&&j<a.length&&containAll(a,i,j)){
if(check(a,i,j)&&j-i+1<len){
len = j - i + 1;
begin = i;
end = j;
}
}
while(j<a.length){
c = a[j];
if(!check(c)){
j++;
continue;
}
if(containAll(a,i,j)){
if(check(a,i,j)&&j-i+1<len){
len = j - i + 1;
begin = i;
end = j;
}
break;
}
j++;
}
}
//print(a,begin,end);
return len==Integer.MAX_VALUE?-1:len;
}
private static void print(char[] a, int begin, int end) {
System.out.print(begin+" "+end);
for(int i = begin;i<=end;i++){
System.out.print(a[i]);
}
}
private static boolean check(char[] a, int i, int j) { int c1 = 0,c2 = 0,c3 = 0; for(int k = i;k<=j;k++){ if(a[k]=='h')c1++; if(a[k]=='i')c2++; if(a[k]=='o')c3++; } return c1==2&&c2==1&&c3==1; }
private static boolean containAll(char[] a, int i, int j) { int c1 = 0,c2 = 0,c3 = 0; for(int k = i;k<=j;k++){ if(a[k]=='h')c1++; if(a[k]=='i')c2++; if(a[k]=='o')c3++; } return c1>=2&&c2>=1&&c3>=1; }
private static boolean check(char c) { return c=='h'||c=='i'||c=='o'; }
package test2; import java.util.Scanner; public class Test{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int res = solve(s);
System.out.println(res);
}
private static int solve(String s) {
char a[] = s.toCharArray();
int j = 0;
int len = Integer.MAX_VALUE;
int begin = 0;
int end = -1;
for(int i = 0;i<s.length();i++){
char c = a[i];
if(!check(c))continue;
if(j==0)j=i+1;
if(j-i+1>=4&&j<a.length&&containAll(a,i,j)){
if(check(a,i,j)&&j-i+1<len){
len = j - i + 1;
begin = i;
end = j;
}
}
while(j<a.length){
c = a[j];
if(!check(c)){
j++;
continue;
}
if(containAll(a,i,j)){
if(check(a,i,j)&&j-i+1<len){
len = j - i + 1;
begin = i;
end = j;
}
break;
}
j++;
}
}
//print(a,begin,end);
return len==Integer.MAX_VALUE?-1:len;
}
private static void print(char[] a, int begin, int end) {
System.out.print(begin+" "+end);
for(int i = begin;i<=end;i++){
System.out.print(a[i]);
}
}
private static boolean check(char[] a, int i, int j) {
int c1 = 0,c2 = 0,c3 = 0;
for(int k = i;k<=j;k++){
if(a[k]=='h')c1++;
if(a[k]=='i')c2++;
if(a[k]=='o')c3++;
}
return c1==2&&c2==1&&c3==1;
}
private static boolean containAll(char[] a, int i, int j) {
int c1 = 0,c2 = 0,c3 = 0;
for(int k = i;k<=j;k++){
if(a[k]=='h')c1++;
if(a[k]=='i')c2++;
if(a[k]=='o')c3++;
}
return c1>=2&&c2>=1&&c3>=1;
}
private static boolean check(char c) {
return c=='h'||c=='i'||c=='o';
}
}