求助一道shortest balanced substring的题！

sylvia2010 发表于 2021-1-6 13:55
得，脸都快被打肿了才写出来。

Sliding window 还是适合有一定 “单调性” 的问题，这个其实没那么合适 ...

谢谢分享！
请教一下：
1. 为什么要再建一个count2呢？
2. if all(count2[c.swapcase()] for c in count2 if count2[c]):是为什么呢？
谢谢！！！

我试着模仿了一个java版本，但是运行结果不对，哪位大神能帮我看看嘛？感觉这道题好难啊

1. public String shortestBalancedString(String s){
   
2.         Map<Character, Integer> count = new HashMap<>();
   
3.         Map<Character, Integer> lastseen = new HashMap<>();
   
4.         int i = 0;
   
5.         int ans = Integer.MAX_VALUE;
   
6.         String res = "";
   
7. 
   
8.         for(int j = 0; j < s.length(); j++){
   
9.             char ch = s.charAt(j);
   
10.             char swapped = convert(ch);
    
11. 
    
12.             count.put(ch,count.getOrDefault(ch,0)+1);
    
13.             lastseen.put(ch, lastseen.getOrDefault(ch, -1));
    
14. 
    
15. //            lastseen.put(swapped, lastseen.getOrDefault(swapped, -1));
    
16. 
    
17.             if(!count.containsKey(swapped) || lastseen.get(swapped) < lastseen.get(ch)){
    
18.                 lastseen.put(ch, j);
    
19.                 continue;
    
20.             }
    
21.             while(i < lastseen.get(s.charAt(i)) || i <= j-ans+1){
    
22.                 count.put(s.charAt(i), count.get(s.charAt(i))-1);
    
23.                 i++;
    
24.             }
    
25. 
    
26.             Map<Character, Integer> count2 = new HashMap<>();
    
27.             count2.putAll(count);
    
28.             for(int k = i; k <= lastseen.get(swapped); k++){
    
29.                 boolean flag = true;
    
30.                 for(char x : count2.keySet()) {
    
31.                     if (!count2.containsKey(convert(x))) {
    
32.                         flag = false;
    
33.                         break;
    
34.                     }
    
35.                 }
    
36.                 if(flag) {
    
37.                     res = s.substring(k, j + 1);
    
38.                     ans = j - k + 1;
    
39.                 }
    
40. 
    
41.                 count2.put(s.charAt(k), count2.get(s.charAt(k))-1);
    
42.             }
    
43.             lastseen.put(ch,j)；
    
44.         }
    
45.         return res;
    
46.     }
    
47. 
    
48. 
    
49.     private char convert(char c){
    
50.         if(Character.isLowerCase(c)){
    
51.             return Character.toUpperCase(c);
    
52.         }
    
53.         return Character.toLowerCase(c);
    
54.     }

复制代码