Showing posts with label strings. Show all posts
Showing posts with label strings. Show all posts

Thursday, 10 December 2015

Game of Thrones - I

Problem Statement
Dothraki are planning an attack to usurp King Robert's throne. King Robert learns of this conspiracy from Raven and plans to lock the single door through which the enemy can enter his kingdom.
door
But, to lock the door he needs a key that is an anagram of a certain palindrome string.
The king has a string composed of lowercase English letters. Help him figure out whether any anagram of the string can be a palindrome or not.
Input Format 
A single line which contains the input string.
Constraints 
1≤ length of string ≤105 
Each character of the string is a lowercase English letter.
Output Format 
A single line which contains YES or NO in uppercase.
Sample Input : 01
aaabbbb
Sample Output : 01
YES
Explanation 
A palindrome permutation of the given string is bbaaabb. 
Sample Input : 02
cdefghmnopqrstuvw
Sample Output : 02
NO
Explanation 
You can verify that the given string has no palindrome permutation. 
Sample Input : 03
cdcdcdcdeeeef
Sample Output : 03
YES
Explanation 
A palindrome permutation of the given string is ddcceefeeccdd

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        String entry = in.next();
        int[] frequency = new int[26];
        for(int i =0; i<entry.length(); i++){
            char ch = entry.charAt(i);
            frequency[ch - 'a']++;
        }
        int countOdd = 0;
        for(int i = 0; i < 26 ; i++){
            if(frequency[i] % 2 != 0){
                countOdd++;
            }
        }
        if(countOdd > 1) System.out.println("NO");
        else System.out.println("YES");
    }
}

Monday, 7 December 2015

Palindrome index

Problem Statement
You are given a string of lower case letters. Your task is to figure out the index of the character on whose removal it will make the string a palindrome. There will always be a valid solution.

In case the string is already a palindrome, then -1 is also a valid answer along with possible indices.
Input Format
The first line contains T, i.e. the number of test cases.
T lines follow, each containing a string.
Output Format
Print the position (0 index) of the letter by removing which the string turns into a palindrome. For a string, such as
bcbc
we can remove b at index 0 or c at index 3. Both answers are accepted.
Constraints
1≤T≤20
1≤ length of string ≤100005
All characters are Latin lower case indexed.
Sample Input
3
aaab
baa
aaa
Sample Output
3
0
-1
Explanation
In the given input, T = 3,
  • For input aaab, we can see that removing b from the string makes the string a palindrome, hence the position 3.
  • For input baa, removing b from the string makes the string palindrome, hence the position 0.
  • As the string aaa is already a palindrome, you can output 0, 1 or 2 as removal of any of the characters still maintains the palindrome property. Or you can print -1 as this is already a palindrome.


JAVA Program 

import java.io.*;
import java.util.*;

public class Solution {
    
    public static int isPallindrome(String string){
        for(int i = 0; i< string.length()/2 ; i++){
            if(string.charAt(i) != string.charAt(string.length() - i -1)){
                return 0;
            }
        }
        return 1;
    }
    public static int pallindromeIndex(String string, int start, int end){
        if(start >= end-1){
            return -1;
        }else{
            if(string.charAt(start) == string.charAt(end-1)){
                return pallindromeIndex(string, start + 1, end - 1);
            }else{
                String temp = string.substring(start , end -1 );
                if(isPallindrome(temp) == 1){
                    return end - 1;
                }else{
                    return start;
                }
            }
        }
       
    }
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int K = in.nextInt();
        for(int i = 0; i<K; i++){
            String string = in.next();
            int index = pallindromeIndex(string, 0, string.length());
            System.out.println(index);
        }
    }
}

================================================================

C Program :

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

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t, i;
    scanf("%d",&t);
    for( i = 0 ; i < t ; i ++ )
        {
        char *in;
        int len, j, k, index = -1; 
        scanf("%ms",&in);
        len = strlen(in);
        j = 0;
        k = len - 1; 
        while( j < len/2 )
            {
            if( in[k] != in[j] )
                {
                if( in[j + 1] == in[k] && in[k - 1] != in[j] )
                    {
                    index = j;
                    break;
                }
                else if( in[j + 1] != in[k] && in[k - 1] == in[j])
                    {
                    index = k;
                    break;
                }               
                else 
                    {
                    int l;
                    for( l = 2 ; j+l < len/2 && in[j+l] == in[k-l-1] ; l++);
                    if(j+l == len/2)
                        {
                        index = k;
                        break;
                    }
                    for( l = 3 ; j+l <= len/2 && in[j+l] == in[k-l+1] ; l++);
                    if(j+l == len/2 + 1)
                        {
                        index = j;
                        break;
                    }
                    
                }
                    
            }
            j++;
            k--;
        }
            printf("%d\n",index);
    }
    return 0;
}

Sunday, 6 December 2015

Two strings substring

Problem Statement
You are given two strings, A and B. Find if there is a substring that appears in both A and B.
Input Format
Several test cases will be given to you in a single file. The first line of the input will contain a single integer T, the number of test cases.
Then there will be T descriptions of the test cases. Each description contains two lines. The first line contains the string A and the second line contains the string B.
Output Format
For each test case, display YES (in a newline), if there is a common substring. Otherwise, display NO.
Constraints
All the strings contain only lowercase Latin letters.
1<=T<=10
1<=|A|,|B|<=105
Sample Input
2
hello
world
hi
world
Sample Output
YES
NO
Explanation
For the 1st test case, the letter o is common between both strings, hence the answer YES. (Furthermore, the letter l is also common, but you only need to find one common substring.)
For the 2nd test case, hi and world do not have a common substring, hence the answer NO.
Copyright © 2015 HackerRank.
All Rights Reserved



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

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t, i;
    scanf("%d",&t);
    for( i = 0 ; i < t ; i++ )
        {
        char * in1, *in2;
        int store[26]={0}, j = 0, flag = 0;
        scanf("%ms",&in1);
        scanf("%ms",&in2);
        while(in1[j] != '\0')
            {
            store[in1[j] - 'a'] ++;
            j++;
        }
        j = 0;
        while(in2[j] != '\0')
            {
            if(store[in2[j] - 'a'] != 0)
                {
                flag = 1 ;
                break;
            }
            j++;
        }
        if(flag == 0)
            {
            printf("NO\n");
        }
        else
            {
            printf("YES\n");
        }
    }
    return 0;
}