You are not logged in. Please login at www.codechef.com to post your questions!

×

EXOCODE3 - Editorial

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[i]%2!=0 && hash[i]!=0) //check the hash array
           cnt++;

    }


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

}

asked 15 Mar '17, 17:49

vivek96's gravatar image

2★vivek96
533221
accept rate: 8%

edited 20 Mar '17, 12:36

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 15 Mar '17, 18:00

adhish_kapoor's gravatar image

3★adhish_kapoor
90410
accept rate: 9%

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

U can see above...which is not a correct solurion

(15 Mar '17, 18:02) adhish_kapoor3★

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
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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