1763. 最长的美好子字符串-贪心算法

1763. 最长的美好子字符串

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，“abABB” 是美好字符串，因为 ‘A’ 和 ‘a’ 同时出现了，且 ‘B’ 和 ‘b’ 也同时出现了。然而，“abA” 不是美好字符串因为 ‘b’ 出现了，而 ‘B’ 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = “YazaAay”
输出：“aAa”
解释：“aAa” 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 ‘a’ 和大写形式 ‘A’ 也同时出现了。
“aAa” 是最长的美好子字符串。

示例 2：

输入：s = “Bb”
输出：“Bb”
解释：“Bb” 是美好字符串，因为 ‘B’ 和 ‘b’ 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = “c”
输出：“”
解释：没有美好子字符串。

示例 4：

输入：s = “dDzeE”
输出：“dD”
解释：“dD” 和 “eE” 都是最长美好子字符串。
由于有多个美好子字符串，返回 “dD” ，因为它出现得最早。

对于这一题，其实，可能很多人都知道怎么做，但是实现起来，需要几个技巧，去方便我们实现算法思想，首先应该设置两个数组去记录字母的出现次数，还有需要在判断是否是美好字符串时设置一个变量去判断，这样实现起来会简单很多，解题代码如下，需要处理的细节也挺多的：

char * longestNiceSubstring(char * s){
    int bpha[26];
    int spha[26];
    for(int i=0;i<26;i++){
        bpha[i]=0;
        spha[i]=0;
    }
  int low=0,high=0,r=1;
  int index=0;
  int max=0;
    for(int i=0;s[i]!='\0';i++){
       
        for(int k=0;k<26;k++){
                bpha[k]=0;
                spha[k]=0;
            }
            int count=0;
        for(int j=i;s[j]!='\0';j++){
                if(s[j]>='a'&&s[j]<='z'){
                    spha[s[j]-'a']++;
                    if(spha[s[j]-'a']==1&&bpha[s[j]-'a']==0){
                        count++;

                    }
                     if(spha[s[j]-'a']==1&&bpha[s[j]-'a']>=1){
                        count--;

                    }
                }
                else{
                    bpha[s[j]-'A']++;
                     if(spha[s[j]-'A']==0&&bpha[s[j]-'A']==1){
                        count++;

                    }
                     if(spha[s[j]-'A']>=1&&bpha[s[j]-'A']==1){
                        count--;

                    }

                }
                if(count==0){
                    if(j-i+1>max){
                        index=i;
                        max=j-i+1;

                    }

                }
          }


    }
    printf("%d %d",index,max);
    s[index+max]='\0';
    return s+index;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59