×

# EXOCODE3 - Editorial

 0 Problem Link:https://www.codechef.com/problems/EXOCODE3 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

 0 @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. answered 15 Mar '17, 18:00 904●10 accept rate: 9% https://www.codechef.com/viewsolution/13076815 U can see above...which is not a correct solurion (15 Mar '17, 18:02) all the queries are resolved during and after contest so no need to repeat one thing again and again,Thanks (15 Mar '17, 18:23) vivek962★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,664
×643
×344
×195
×24

question asked: 15 Mar '17, 17:49

question was seen: 498 times

last updated: 20 Mar '17, 12:36