Palindrome Rearrange

January 16, 2023

Name: Moch Lutfi
Twitter: @kaptenupi

Problem

Given a string, find out if its characters can be rearranged to form a palindrome.

Example

For inputString = "aabb", the output should be solution(inputString) = true.

We can rearrange "aabb" to make "abba", which is a palindrome.

Solution

The condition of string to become palindrome is all character count must be even and only allow maximum 1 odd character. For example:

aabb -> abba or baab a = 2 b = 2
aaabb -> ababa or baaab a = 3 b = 2

Using hash byte of int to store character frequency
Loop inputString to counter total char

solution.go

func solution(inputString string) bool {
    charCount := make(map[byte]int)
    for i := range inputString {
        charCount[inputString[i]]++
    }
    oddCount := 0
    for _, count := range charCount {
        if count%2 == 1 {
            oddCount++
        }
    }
    return oddCount <= 1
}

Init total odd frequency as zero.

solution.go

func solution(inputString string) bool {
    charCount := make(map[byte]int)
    for i := range inputString {
        charCount[inputString[i]]++
    }
    oddCount := 0
    for _, count := range charCount {
        if count%2 == 1 {
            oddCount++
        }
    }
    return oddCount <= 1
}

Iterate hash charCount to find out how many odd frequency.

solution.go

func solution(inputString string) bool {
    charCount := make(map[byte]int)
    for i := range inputString {
        charCount[inputString[i]]++
    }
    oddCount := 0
    for _, count := range charCount {
        if count%2 == 1 {
            oddCount++
        }
    }
    return oddCount <= 1
}

Return true if odd frequency is less than equals 0

solution.go

func solution(inputString string) bool {
    charCount := make(map[byte]int)
    for i := range inputString {
        charCount[inputString[i]]++
    }
    oddCount := 0
    for _, count := range charCount {
        if count%2 == 1 {
            oddCount++
        }
    }
    return oddCount <= 1
}

Using hash byte of int to store character frequency
Loop inputString to counter total char

Init total odd frequency as zero.

Iterate hash charCount to find out how many odd frequency.

Return true if odd frequency is less than equals 0

solution.go

func solution(inputString string) bool {
    charCount := make(map[byte]int)
    for i := range inputString {
        charCount[inputString[i]]++
    }
    oddCount := 0
    for _, count := range charCount {
        if count%2 == 1 {
            oddCount++
        }
    }
    return oddCount <= 1
}

What company you must choose ?Iterate digit by given integer