Problem Link:https://www.codechef.com/problems/EXOCODE3
Author:https://www.codechef.com/users/vivek96
DIFFICULTY:Medium
PREREQUISITES:Algorithms,Hashing,Array,String
PROBLEM:Chef like palindrome strings more than normal trings ,so chef Just want to check if characters of a given string can be rearranged to form a palindrome string or not.
Help him to check, print YES if its possible,else print NO
EXPLANATION:
Palindrome String:A string is said to be palindrome if reverse of the string is same as string. For example, “abba” is palindrome, but “abbc” is not palindrome
A set of characters can form a palindrome if at most one character occurs odd number of times and all characters occur even number of times.
A simple solution is to run two loops, the outer loop picks all characters one by one, the inner loop counts number of occurrences of the picked character. We keep track of odd counts. Time complexity of this solution is O(n^2),This will lead to tle(Time Limit Exceeded)
We can do it in O(n) time using a hash array. Following are detailed steps.
-
Create a hash array,which is typically of size 26 because string “s” will contains only lowercase alphabets. Initialize all values of count array as 0.
-
Traverse the given string and increment count of every character.
-
Traverse the hash array if the hash array has less than or equal to one odd value then answer is YES else NO
AUTHOR’S AND TESTER’S SOLUTIONS:
import java.util.Scanner;
class chefandpalindrome
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String s=sc.next();
int hash[]=new int[26];
for(int i=0;i<s.length();i++)
{
hash[s.charAt(i)-97]++; //hashing is done here
}
int cnt=0;
for(int i=0;i<26;i++)
{
if(hash[i]%2!=0 && hash[i]!=0) //check the hash array
cnt++;
}
if(cnt<=1)
System.out.println("YES");
else
System.out.println("NO");
}
}