Very concise Java 14 lines


  • 0
    W
    There are 3 cases
      1 s.length < 6
      2 s.length > 20
      3 s.length is valid
    Case 1 we need insert operation, note that when we insert a character, the type count increases by one if the type count is less than 3. Because we can insert an character of unused type. For example, password "aac12", we can insert an upper character 'A' to make it strong.
    Case 2 we need delete operation, it is obvious that we should delete characters which repeat  in a row first. For examlple, "123456789012345678Baa", we should delete an 'a'.
    Case 3 the length is valid, the only problem is to make sure 
        1 there are 3 types 
        2 there are no 3 or more repeating characters in a row
    To avoid repeating ones, we can use insert, delete, change all 3 ways. But it is obvious we should just use change. 
    Because
      1 delete and insert will change the length so you may have to worry about the length becomes invalid again.
      2 change is more effcient, using change we can handle 5 'aaaaa' to 'aabaa', when insert can only handle 4 and delete only 3.
        delete 3 'aaa' -> 'aa' and insert 4 'aaaa' -> 'aabaa' 
    It is obvious that like insert change can also increase type count.
    Then we have only one problem, how many change operations we need to handle [a]{n} pattern?
    It is obvious the answer is n/3.     
    
    public int strongPasswordChecker(String s) {
      PriorityQueue<Integer> repeats = new PriorityQueue<>((i1, i2) -> (i1 % 3) - (i2 % 3));
      int low = 0, up = 0, digit = 0;// 0 for not occurs 1 for for already have one 
      for (int i = 0, j, c, repeat; i < s.length(); i = j) {
        if ((c = s.charAt(i)) >= 'a' && c <= 'z') low = 1;
        else if (c >= 'A' && c <= 'Z') up = 1;
        else if (c >= '0' && c <= '9') digit = 1;
        for (j = i + 1; j < s.length() && c == s.charAt(j); j++);
        if ((repeat = j - i) > 2) repeats.add(repeat);
      }
      int len = s.length(), count = 0, delete = len - 20, insert = 6 - len, type = 3 - low - up - digit, top, change;
      for (; !repeats.isEmpty() && delete-- > 0; count++)//delete operation
        if ((top = repeats.poll()) > 3) repeats.add(--top);
      for (; !repeats.isEmpty() && insert-- > 0; type--, count++)//insert operation
        if ((top = repeats.poll()) > 4) repeats.add(top - 2);
      return (change = repeats.stream().mapToInt(i -> i / 3).sum()) + Math.max(0, delete) + Math.max(0, Math.max(insert, type - change)) + count;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.