PROBLEM LINK:
Author: Akash Kumar Bhagat
Tester: Sandeep Singh,Arnab Chanda
Editorialist: Akash Kumar Bhagat
Video Explanation: Youtube Link
DIFFICULTY:
Easy
PREREQUISITES:
Strings
PROBLEM:
To find the length of the longest palindrome prefix for the given string.
EXPLANATION:
As the constrain of the string is low, we can easily compare each substring/prefix of the given string to be a palindrome or not. One can start from the end and check each prefix to be a palindrome. If any prefix is found to be a palindrome, then print the length of the prefix.
Do share your approach to the problem in the comment section .
SOLUTIONS:
Python 3.7
for _ in range(int(input())):
s=input()
for i in range(len(s),-1,-1):
if(s[:i]==s[:i][::-1]):
print(i)
break
CPP
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
bool isPalindrome(string& A,int l, int r)
{
while (r > l)
{
if (A[l++] != A[r--])
return false;
}
return true;
}
void solve(){
int n,i,j;
string st;
cin>>st;
n = st.length();
for(i=n-1;i>0;i--){
if(isPalindrome(st,0,i)){
cout<<i+1<<endl;
return;
}
}
cout<<1<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t;
cin>>t;
while(t--)
solve();
}
JAVA
/*
Arnab Chanda
*/
// All imports here
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;
import java.util.*;
import java.util.stream.Collectors;
// Template code starts here //
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Debugger debug = new Debugger(out);
Objectify objectify = new Objectify(debug);
Task solver = new Task();
int test = in.nextInt();
while(test-->0){
solver.solve(1, in, out, debug, objectify);
}
out.close();
}
}
class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
class Debugger{
PrintWriter out;
Debugger(PrintWriter out){
this.out = out;
}
public <T> void printList(List<T> arrayList){
for( Object ob: arrayList){
out.print(ob+" ");
}
out.println();
}
public <T> void printSet(Set<T> set){
for(Object ob: set){
out.print(ob+" ");
}
out.println();
}
public <T> void printMap(Map<?,?> map){
for(Object ob: map.keySet()){
System.out.println(ob+" : "+map.get(ob));
}
}
}
class Objectify{
Debugger debug;
Objectify(Debugger ob){ debug = ob; }
public void printArr(int[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
public void printArr(double[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
public void printArr(long[] arr){ debug.printList(Arrays.stream(arr).boxed().collect(Collectors.toList())); }
public void printArr(char[] arr){ debug.printList( String.valueOf(arr).chars().mapToObj(c -> (char) c).collect(Collectors.toList())); }
public void printArr(String[] arr){ debug.printList(Arrays.asList(arr)); }
public void printMatrix(int[][] arr){ for(int a[]:arr) printArr(a); }
public void printMatrix(double[][] arr){ for(double a[]:arr) printArr(a); }
public void printMatrix(long[][] arr){ for(long a[]:arr) printArr(a); }
public void printMatrix(char[][] arr){ for(char a[]:arr) printArr(a); }
public void printMatrix(String[][] arr){ for(String a[]:arr) printArr(a); }
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Template code ends here
class Task {
final long MOD = (int)Math.pow(10,9)+7;
public void solve(int testNumber, InputReader sc, PrintWriter out, Debugger debug, Objectify objectify) {
// write your code here
String s = sc.next();
int ptr1 = 0, ptr2 = s.length()-1, n = s.length();
List<Integer> a = new ArrayList<>();
for(int i = 0;i<n;++i){
char c = s.charAt(i);
if (c == s.charAt(ptr1)) a.add(i);
}
for(int i = a.size()-1;i>=0;i--){
ptr1 = 0;
ptr2 = a.get(i);
int flag = 0;
while(ptr1<ptr2){
if (s.charAt(ptr1) != s.charAt(ptr2)){
flag = 1;
break;
}
else{
ptr1++;
ptr2--;
}
}
if(flag == 0){
ptr2 = a.get(i);
break;
}
}
out.println(ptr2+1);
}
}