CODEWITHSUNDEEP
palindrome
Vaibhav
Vaibhav

Reputation: 61

How to determine if a string can be manipulated to be rewritten as a palindrome?

I believe this can be achieved by counting the instances for each character in that string. Even if a single character in that string is repeated at least twice, we can declare that string as a palindrome.

For example: bbcccc can be rewritten as bccccb or ccbbcc. edified can be rewritten as deified.

Some book mentioned we should be using hash table. I think we can just use a list and check for the character count.

Do you think the logic is correct?

Upvotes: 1

Views: 4093

Answers (8)

Yusufu
Yusufu

Reputation: 115

My code check if can it is palindrome or can be manipulated to Palindrome

    #include <stdio.h>
    #include <string.h>
    #include <stdbool.h>

    //Tested on windows 64 bit arhc by using cygwin64 and GCC

    bool isPalindrome (char *text);

    int main()
    {
       char text[100]; // it could be N with defining N

       bool isPal,isPosPal = false;
       printf("Give me a string to test if it is Anagram of Palindrome\n");
       gets(text);
     
       isPal = isPalindrome(text);
       isPosPal = isAnagramOfPalindrome(text);
       if(isPal == false)
        {
            printf("Not a palindrome.\n");
        }
        else
        {
            printf("Palindrome.\n");
        }
       if(isPosPal == false)
        {
            printf("Not Anagram of Palindrome\n");
        }
        else
        {
            printf("Anagram of Palindrome\n");
        }
     
       return 0;
    }


    bool isPalindrome (char *text) {
       int begin, middle, end, length = 0;

       length = getLength(text);
       end = length - 1;
       middle = length/2;
     
       for (begin = 0; begin < middle; begin++)
       {
          if (text[begin] != text[end])
          {
               return false;        
          }
          end--;
       }
       if (begin == middle)
          return true;
    }

    int getLength (char *text) { 
       int length = 0;
       while (text[length] != '\0')
       length++;
       printf("length: %d\n",length);
       return length;
    }

    int isAnagramOfPalindrome (char *text) { 

        int length = getLength(text);
        int i = 0,j=0;
        bool arr[26] = {false};
        int counter = 0;
        //char string[100]="neveroddoreven";
        int a;
        

        
        for (i = 0; i < length; i++)
        {
            a = text[i];
            a = a-97;

            if(arr[a])
            {
                arr[a] = false;
            }
            else
            {
                arr[a] = true;
            }
        }
        
        for(j = 0; j < 27 ; j++)
        {
            if (arr[a] == true)
            {
                counter++;
            }
        }
        
        printf("counter: %d\n",counter);
        if(counter > 1)
        {
            return false;
        }
        else if(counter == 1)
        {
            if(length % 2 == 0)
                return false;
            else
                return true;
        }
        else if(counter == 0)
        {
            return true;
        }
        
    }

Upvotes: 1

Prashant Shubham
Prashant Shubham

Reputation: 516

Any string can be palindrome only if at most one character occur odd no. of times and all other characters must occur even number of times. The following program can be used to check whether a palindrome can be string or not. 

vector<int> vec(256,0); //Vector for all ASCII characters present.
for(int i=0;i<s.length();++i)
{
    vec[s[i]-'a']++;
}
int odd_count=0,flag=0;
for(int i=0;i<vec.size();++i)
{
    if(vec[i]%2!=0)
        odd_count++;
    if(odd_count>1)
    {
        flag=1;
        cout<<"Can't be palindrome"<<endl;
        break;  
    }
}
if(flag==0)
    cout<<"Yes can be palindrome"<<endl;

Upvotes: 1

gokool
gokool

Reputation: 1

Assuming all input characters are lower case letters. 

#include<stdio.h>

int main(){

char *str;
char arr[27];
int j;
int a;
j = 0;
printf("Enter the string : ");
scanf("%s", str);
while (*str != '\0'){
    a = *str;
    a = a%27;

    if(arr[a] == *str){
        arr[a]=0;
        j--;
    }else{
        arr[a] = *str;
        j++;
    }
    *str++;
}
if(j==0 || j== -1 || j==1){
    printf ("\nThe string can be a palindrome\n");

}
}

Upvotes: 0

l33t
l33t

Reputation: 19937

C#:

bool ok = s.GroupBy(c => c).Select(g => g.Count()).Where(c => c == 1).Count() < 2;

This solution, however, does use hashing.

Upvotes: 0

Marichyasana
Marichyasana

Reputation: 3154

Here is a simple solution using an array; no sort needed

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a[256] = { 0 };
    unsigned char i[] = {"aaBcBccc"};
    unsigned char *p = &i[0];
    int c = 0;
    int j;
    int flag = 0;
    while (*p != 0)
    {
        a[*p]++;
        p++;
    }
    for(j=0; j<256; j++)
    {
        if(a[j] & 1)
        {
            c++;
            if(c > 1)
            {
                flag = 1;
                break;
            }
        }
    }
    if(flag)
        printf("Nope\n");
    else
        printf("yup\n");
return 0;

}

Upvotes: 0

SeeMoreGain
SeeMoreGain

Reputation: 1273

as others have posted, the idea is to have each character occur an even number of times for an even length string, and one character an odd number of times for an odd length string.

The reason the books suggest using a hash table is due to execution time. It is an O(1) operation to insert into / retrieve from a hash map. Yes a list can be used but the execution time will be slightly slower as the sorting of the list will be O(N log N) time.

Pseudo code for a list implementation would be:

sortedList = unsortedList.sort;

bool oddCharFound = false;

//if language does not permit nullable char then initialise 
//current char to first element, initialise count to 1 and loop from i=1
currentChar = null;
currentCharCount = 0;
for (int i=0; i <= sortedList.Length; i++) //start from first element go one past end of list
{
    if(i == sortedList.Length 
        || sortedList[i] != currentChar)
    {
        if(currentCharCount % 2 = 1)
        {
            //check if breaks rule
            if((sortedList.Length % 2 = 1 && oddCharFound)
                || oddCharFound)
            {
                return false;
            }
            else
            {
                oddCharFound = true;
            }
        }
        if(i!= sortedList.Length)
        {
            currentCharCount = 1;
            currentChar = sortedList[i];
        }

    }
    else
    {
        currentCharCount++;
    }
}
return true;

Upvotes: 0

Jess
Jess

Reputation: 25069

No. You don't have to use a hash map (as some of the other answers suggest). But the efficiency of the solution will be determined by the algorithm you use.

Here is a solution that only tracks odd characters. If we get 2 odds, we know it can't be a scrambled palindrome. I use an array to track the odd count. I reuse the array index 0 over and over until I find an odd. Then I use array index 1. If I find 2 odds, return false!

Solution without a hash map in javascript:

function isScrambledPalindrome(input) {
    // TODO: Add error handling code.
    var a = input.split("").sort();
    var char, nextChar = "";
    var charCount = [ 0 ];
    var charIdx = 0;
    for ( var i = 0; i < a.length; ++i) {
        char = a[i];
        nextChar = a[i + 1] || "";
        charCount[charIdx]++;
        if (char !== nextChar) {
            if (charCount[charIdx] % 2 === 1) {
                if (charCount.length > 1) {
                    // A scrambled palindrome can only have 1 odd char count.
                    return false;
                }
                charIdx = 1;
                charCount.push(0);
            } else if (charCount[charIdx] % 2 === 0) {
                charCount[charIdx] = 0;
            }
        }
    }
    return true;
}

console.log("abc: " + isScrambledPalindrome("abc")); // false
console.log("aabbcd: " + isScrambledPalindrome("aabbcd")); // false
console.log("aabbb: " + isScrambledPalindrome("aabbb")); // true
console.log("a: " + isScrambledPalindrome("a")); // true

Using a hash map, I found a cool way to only track the odd character counts and still determine the answer.

Fun javascript hash map solution:

function isScrambledPalindrome( input ) { 
    var chars = {}; 
    input.split("").forEach(function(char) { 
    if (chars[char]) { 
        delete chars[char] 
    } else { 
        chars[char] = "odd" } 
    }); 
    return (Object.keys(chars).length <= 1); 
}

isScrambledPalindrome("aba"); // true
isScrambledPalindrome("abba"); // true
isScrambledPalindrome("abca"); // false

Upvotes: 1

herohuyongtao
herohuyongtao

Reputation: 50667

Yes, the main idea is to count the times of each char existing in the string. And it will be true if the string has at most one char occurs odd times and all others even times.

For example:

  1. aabbcc => acbbca

  2. aabcc => acbca

  3. aabbb => abbba

Upvotes: 2

Related Questions