Java Solution - Use the Boolean Array


  • 0
    J

    To construct palindrome: we can make use of all the char that appear even times, and take one from the char that appear ood times.

    if N(char appearing odd times) > 0
        LengthOfPalindrome = N(char appearing even times) + N(char appearing odd times) + 1
    else
        LengthOfPalindrome = s.length()
    

    We need to know how many char in the String appears odd times.
    Actually, we do not need to really keep how many times each char appear, we just need to know whether it is odd or even.
    Therefore, give each alphabet(lower case and upper case) a boolean to do the book keeping is enough. Every time we see the char appearing, we flip the boolean value.

    public class Solution {
        public int longestPalindrome(String s) {
            int L = s.length();
            boolean [] m = new boolean[52];
            
            for(char ch : s.toCharArray()) {
                if(ch >= 'a' && ch <= 'z') {
                    m[ch-'a'] = !m[ch-'a'];
                } else {
                    m[ch-'A'+26] = !m[ch-'A'+26];
                }
            }
            
            int odd = 0;
            for(boolean f : m) {
                if(f) {
                    odd ++;
                }
            }
            
            if(odd == 0) {
                return L;
            } else {
                return L - odd + 1;
            }
        }
    }
    

    Time complexity O(N)
    Space complexity O(1)


Log in to reply
 

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