EXOCODE3 - Editorial

algorithm
editorial
hashing
important
palindrome
string

#1

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.

  1. 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.

  2. Traverse the given string and increment count of every character.

  3. 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*%2!=0 && hash*!=0) //check the hash array
           cnt++;

    }
    
    
    if(cnt<=1)
        System.out.println("YES");
    else
        System.out.println("NO");
        }

}


#2

@vivek96
Now the above code is absolutely correct…but during the contest I submitted the above code 6-7 times…it was showing WA
It means your test cases were not correct at that time…and when I submitted with condition count==1 it gave me AC.


#3

https://www.codechef.com/viewsolution/13076815

U can see above…which is not a correct solurion


#4

all the queries are resolved during and after contest so no need to repeat one thing again and again,Thanks