Java 1ms solution without using Set nor Map, but a Boolean array with only one O(n) loop.


  • 0

    Key points:

    1. Using Boolean to count the appearance of each char is enough since we only need to know it is odd or even.

    2. When counting numbers of odd char, +1 when odd, -1 when even within each iteration.

      public class Solution {
      public boolean canPermutePalindrome(String s) {
      int len = s.length();
      if (len <= 1) return true;
      boolean[] isodd = new boolean[256];
      int odds = 0;
      for ( char c: s.toCharArray() ) {
      isodd[c] = !isodd[c];
      if ( isodd[c] ) {
      odds++;
      } else {
      odds--;
      }
      }
      return odds <=1 ;
      }
      }


Log in to reply
 

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