Skip to content

Instantly share code, notes, and snippets.

@urschrei
Last active September 25, 2018 12:24
Show Gist options
  • Save urschrei/000b9d69027d3e6cce9fee811e8cd57e to your computer and use it in GitHub Desktop.
Save urschrei/000b9d69027d3e6cce9fee811e8cd57e to your computer and use it in GitHub Desktop.
Detect whether an (extended) ASCII string is a palindrome anagram using Rust
// Given a string, how do you determine whether it's an anagram of a palindrome?
// Solution: Given the unique set of chars, at most 1 should appear in the string
// an odd number of times.
// chars() returns Unicode Scalar Values, and these might not match up
// with grapheme clusters, so this can't be assumed to work correctly
// for anything other than (extended) ASCII
fn unique_chars(s: &str) -> String {
let mut v: Vec<char> = s.chars().collect();
// dedup removes consecutive identical elements, so we need a sort first
v.sort_unstable();
v.dedup();
v.into_iter().collect()
}
/// Count the number of odd occurrences of each unique char in the string
/// If the sum is greater than 1, no palindrome is possible
fn possible_palindrome(letters: &str) -> bool {
let uniq = unique_chars(letters);
uniq.chars()
.map(|char| letters.matches(char).count() % 2)
.sum::<usize>()
<= 1
}
fn main() {
let pal = "ABBBBAF";
let npal = "DABBAF";
assert_eq!(possible_palindrome(pal), true);
assert_eq!(possible_palindrome(npal), false);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment