Shortest Palindromic Substring
Last Updated :
29 Dec, 2022
Given a string you need to find the shortest palindromic substring of the string. If there are multiple answers output the lexicographically smallest.
Examples:
Input: zyzz
Output:y
Input: abab
Output: a
Naive Approach:
- The approach is similar to finding the longest palindromic substring. We keep track of even and odd lengths substring and keep storing it in a vector.
- After that, we will sort the vector and print the lexicographically smallest substring. This may also include empty substrings but we need to ignore them.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
string ShortestPalindrome(string s)
{
int n = s.length();
vector<string> v;
for (int i = 0; i < n; i++)
{
int l = i;
int r = i;
string ans1 = "";
string ans2 = "";
while (l >= 0 && r < n && s[l] == s[r])
{
ans1 += s[l];
l--;
r++;
}
l = i - 1;
r = i;
while (l >= 0 && r < n && s[l] == s[r])
{
ans2 += s[l];
l--;
r++;
}
v.push_back(ans1);
v.push_back(ans2);
}
string ans = v[0];
for (int i = 0; i < v.size(); i++)
{
if (v[i] != "")
{
ans = min(ans, v[i]);
}
}
return ans;
}
int main()
{
string s = "geeksforgeeks";
cout << ShortestPalindrome(s);
return 0;
}
|
Java
import java.util.*;
import java.io.*;
class GFG{
public static String ShortestPalindrome(String s)
{
int n = s.length();
Vector<String> v = new Vector<String>();
for(int i = 0; i < n; i++)
{
int l = i;
int r = i;
String ans1 = "";
String ans2 = "";
while (l >= 0 && r < n &&
s.charAt(l) == s.charAt(r))
{
ans1 += s.charAt(l);
l--;
r++;
}
l = i - 1;
r = i;
while (l >= 0 && r < n &&
s.charAt(l) == s.charAt(r))
{
ans2 += s.charAt(l);
l--;
r++;
}
v.add(ans1);
v.add(ans2);
}
String ans = v.get(0);
for(int i = 0; i < v.size(); i++)
{
if (v.get(i) != "")
{
if (ans.charAt(0) >=
v.get(i).charAt(0))
{
ans = v.get(i);
}
}
}
return ans;
}
public static void main(String []args)
{
String s = "geeksforgeeks";
System.out.println(ShortestPalindrome(s));
}
}
|
Python3
def ShortestPalindrome(s) :
n = len(s)
v = []
for i in range(n) :
l = i
r = i
ans1 = ""
ans2 = ""
while ((l >= 0) and (r < n) and (s[l] == s[r])) :
ans1 += s[l]
l -= 1
r += 1
l = i - 1
r = i
while ((l >= 0) and (r < n) and (s[l] == s[r])) :
ans2 += s[l]
l -= 1
r += 1
v.append(ans1)
v.append(ans2)
ans = v[0]
for i in range(len(v)) :
if (v[i] != "") :
ans = min(ans, v[i])
return ans
s = "geeksforgeeks"
print(ShortestPalindrome(s))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static string ShortestPalindrome(string s)
{
int n = s.Length;
List<string> v = new List<string>();
for(int i = 0; i < n; i++)
{
int l = i;
int r = i;
string ans1 = "";
string ans2 = "";
while(l >= 0 && r < n && s[l] == s[r])
{
ans1 += s[l];
l--;
r++;
}
l = i - 1;
r = i;
while(l >= 0 && r < n && s[l] == s[r])
{
ans2 += s[l];
l--;
r++;
}
v.Add(ans1);
v.Add(ans2);
}
string ans = v[0];
for(int i = 0; i < v.Count; i++)
{
if(v[i] != "")
{
if(ans[0] >= v[i][0])
{
ans = v[i];
}
}
}
return ans;
}
static public void Main ()
{
string s = "geeksforgeeks";
Console.WriteLine(ShortestPalindrome(s));
}
}
|
Javascript
<script>
function ShortestPalindrome(s)
{
let n = s.length;
let v = [];
for(let i = 0; i < n; i++)
{
let l = i;
let r = i;
let ans1 = "";
let ans2 = "";
while(l >= 0 && r < n && s[l] == s[r])
{
ans1 += s[l];
l--;
r++;
}
l = i - 1;
r = i;
while(l >= 0 && r < n && s[l] == s[r])
{
ans2 += s[l];
l--;
r++;
}
v.push(ans1);
v.push(ans2);
}
let ans = v[0];
for(let i = 0; i < v.length; i++)
{
if(v[i] != "")
{
if(ans[0] >= v[i][0])
{
ans = v[i];
}
}
}
return ans;
}
let s = "geeksforgeeks";
document.write(ShortestPalindrome(s));
</script>
|
Time Complexity: O(N^2), where N is the length of the string.
Auxiliary Space: O(N^2)
Efficient Approach: An observation here is that a single character is also a palindrome. So, we just need to print the lexicographically smallest character present in the string.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
char ShortestPalindrome(string s)
{
int n = s.length();
char ans = s[0];
for(int i = 1; i < n ; i++)
{
ans = min(ans, s[i]);
}
return ans;
}
int main()
{
string s = "geeksforgeeks";
cout << ShortestPalindrome(s);
return 0;
}
|
Java
class GFG{
static char ShortestPalindrome(String s)
{
int n = s.length();
char ans = s.charAt(0);
for(int i = 1; i < n; i++)
{
ans = (char) Math.min(ans, s.charAt(i));
}
return ans;
}
public static void main(String[] args)
{
String s = "geeksforgeeks";
System.out.print(ShortestPalindrome(s));
}
}
|
Python3
def ShortestPalindrome(s):
n = len(s)
ans = s[0]
for i in range(1, n):
ans = min(ans, s[i])
return ans
s = "geeksforgeeks"
print(ShortestPalindrome(s))
|
C#
using System;
class GFG{
static char ShortestPalindrome(String s)
{
int n = s.Length;
char ans = s[0];
for(int i = 1; i < n; i++)
{
ans = (char) Math.Min(ans, s[i]);
}
return ans;
}
public static void Main(String[] args)
{
String s = "geeksforgeeks";
Console.Write(ShortestPalindrome(s));
}
}
|
Javascript
<script>
function ShortestPalindrome(s)
{
let n = s.length;
let ans = s[0].charCodeAt();
for(let i = 1; i < n; i++)
{
ans = Math.min(ans, s[i].charCodeAt());
}
return String.fromCharCode(ans);
}
let s = "geeksforgeeks";
document.write(ShortestPalindrome(s));
</script>
|
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...