Palindrome Index
Problem Statement :
Given a string of lowercase letters in the range ascii[a-z], determine the index of a character that can be removed to make the string a palindrome. There may be more than one solution, but any will do. If the word is already a palindrome or there is no solution, return -1. Otherwise, return the index of a character to remove. Example s = "bcbc" Either remove 'b' at index 0 or 'c' at index 3. Function Description Complete the palindromeIndex function in the editor below. palindromeIndex has the following parameter(s): string s: a string to analyze Returns int: the index of the character to remove or -1. Input Format The first line contains an integer q, the number of queries. Each of the next q lines contains a query string s. Constraints 1 <= q <= 20 1 <= length of s <= 10^5 + 5 All characters are in the range ascii[a-z].
Solution :
Solution in C :
In C++ :
#include<stdio.h>
#include<string.h>
char a[1000005];
char b[1000005];
int is(char *a, int n){
int i;
for(i=0;i<n/2;i++)if(a[i]!=a[n-1-i])return i;
return -1;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",&a);
int l = strlen(a);
int x = is(a,l);
if(x==-1){
printf("-1\n");
}
else {
int i;
int j=0;
for(i=0;a[i];i++){
if(i!=x)b[j++] = a[i];
}
if(is(b,l-1)==-1)printf("%d\n",x);
else printf("%d\n",l-1-x);
}
}
}
In Java :
import java.util.*;
public class Solution {
static boolean isPalidrom(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int t = 0; t < T; t++) {
String s = in.next();
int i = 0;
int j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
if (isPalidrom(s,i,j-1)) {
System.out.println(j);
} else {
System.out.println(i);
}
break;
}
i ++;
j --;
}
if (i >= j) {
System.out.println(-1);
}
}
}
}
In C :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int t,i,flag,len,ans,j,stop;
char *str;
str = (char *) malloc(sizeof(char)*100005);
scanf("%d",&t);
while(t>0)
{
scanf("%s",str);
len=strlen(str);
ans=-1;
stop=0;
flag=1;
while(stop==0)
{
i=0;
while(i<len/2 && ans==-1)
{
if(str[i]!=str[len-i-1])
{
ans=i;
j=i+1;
while(j<=len/2 && flag==1)
{
if(str[j]!=str[len-j])
{
flag=0;
}
j++;
}
if(flag==1)
{
stop=1;
}
else
flag=1;
if(stop==0)
{
ans=len-i-1;
j=i;
while(j<=len/2 && flag==1)
{
if(str[j]!=str[len-j-2])
{
flag=0;
}
j++;
}
if(flag==1)
{
stop=1;
}
else
flag=1;
}
}
i++;
}
if(ans==-1)
{
stop=1;
}
}
printf("%d\n",ans);
t--;
}
return 0;
}
In Python3 :
t = int(input())
def is_palindrome(s):
return s == s[::-1]
def solve(s):
i, j = 0, len(s) - 1
while (i < j) and (s[i] == s[j]):
i += 1
j -= 1
if i == j:
return 0
if is_palindrome(s[i + 1 : j + 1]):
return i
if is_palindrome(s[i:j]):
return j
raise AssertionError
for _ in range(t):
print(solve(input()))
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →