Published on

Palindrome Rearrange

Authors

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

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

Init total odd frequency as zero.

solution.go

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

Iterate hash charCount to find out how many odd frequency.

solution.go

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

Return true if odd frequency is less than equals 0

solution.go

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

  • 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
ExpandClose

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