Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
The following code does it. Not sure about the complexity though
static int lengthLargestPalindrome(String x){
StringBuilder sb = new StringBuilder(x);
String orig = sb.toString();
String rev = sb.reverse().toString();
if(orig.equals(rev)){
return orig.length();
}
return Math.max(lengthLargestPalindrome(x.substring(1)), lengthLargestPalindrome(x.substring(0,x.length()-1)));
}
Manacher algorithm is what you are looking for. Here is the link: http://en.wikipedia.org/wiki/Longest_palindromic_substring
Unfortunately it is O(n^2) even with a lot of optimizations but at least the memory cost is O(1):
public String largestPalen(String str){
String largest = "";
char[] chars = str.getChars();
for(int left = 0; left < str.length(); left++){
for(int right = str.length()-1; right >= left; right--){
if(isPalen(chars, left, right)){
if(right - left > largest.length){
largest = str.subString(left, right);
}
break;
}
}
if(largest.length() >= str.length() - left){
break;
}
}
return largest;
}
private boolean isPalen(char[] chars, int lo, int hi){
while(lo < hi){
if(chars[lo++] != chars[hi--]){
return false;
}
}
return true;
}
public class Palindrome {
/**
* Returns the longest palindrome.
* @param str the string to check
* @return the longest palindrome
*/
public static String findMaxPalindrome(String str) {
String max = "";
int maxLength = 0;
for (int i = 0; i < str.length(); i++) {
// palindrome only starts with a letter.
if (!Character.isLetter(str.charAt(i))) continue;
for (int j = i + maxLength; j < str.length(); j++) {
// palindrome only ends with a letter.
if (!Character.isLetter(str.charAt(j))) continue;
// get substring length without space
int count = getSubstringLength(str, i, j);
if (count > maxLength && isPalindrome(str, i, j)) {
max = str.substring(i, j+1);
maxLength = count;
}
}
}
return max;
}
/**
* returns the number of letter chars in the sub string from the index i
* to the index j.
* @param str the string to checl
* @param i the start index
* @param j the end index
* @return the number of letters.
*/
private static int getSubstringLength(String str, int i, int j) {
int count = 0;
for (int k = i; k < j; k++) {
if (Character.isLetter(str.charAt(k))) count++;
}
return count;
}
/**
* Check if the substring (from i to j) is a palindrome.
* Use recurcivity.
* @param str the string to check
* @param i the start index
* @param j the end index
* @return true if it is a palindrome, false otherwise.
*/
private static boolean isPalindrome(String str, int i, int j) {
if (j <= i) return true;
if (!Character.isLetter(str.charAt(i))) return isPalindrome(str, i+1, j);
if (!Character.isLetter(str.charAt(j))) return isPalindrome(str, i, j-1);
return Character.toLowerCase(str.charAt(i)) == Character.toLowerCase(str.charAt(j))
&& isPalindrome(str, i+1, j-1);
}
/**
* Main
* @param args
*/
public static void main(String[] args) {
String str = "Hi Anna! A Toyota’s a Toyota. Do you agree?";
String palindrome = findMaxPalindrome(str);
System.out.println(palindrome); // => A Toyota’s a Toyota
}
}
String longestPalindrome(String given) {
if(given == null || given.equals("")) {
return "empty";
}
int[][] lengthMatrix = new int[given.length()][given.length()];
for(int i=0; i< given.length(); i++) {
for(int j=0; j< given.length(); j++) {
if(i==j) {
lengthMatrix[i][j] = 1;
}
else {
lengthMatrix[i][j] = 0;
}
}
}
int max=1, startIndex=0, endIndex=0;
String normalize = given.toLowerCase();
for(int len= 2; len<= given.length(); len++) {
for(int j=0; j<= given.length() - len; j++) {
if(normalize.charAt(j) == normalize.charAt(j+len-1)) {
if(len == 2) {// boundary case
lengthMatrix[j][j+len-1] = 2;
max = len; startIndex = j; endIndex = j+len-1;
}
else if(lengthMatrix[j+1][j+len-2] != 0) {
lengthMatrix[j][j+len-1] = len;
max = len; startIndex = j; endIndex = j+len-1;
}
}
}
}
return given.substring(startIndex, endIndex+1);
}
Javascript code - Can we do it better than O(n2)?
function isPlaindrome(str) {
var i = 0;
var j = str.length - 1;
while (i < j) {
if (str[i] === str[j]) {
i++;
j--;
} else {
return false;
}
}
return true;
}
function getAllPossibleSubstrings(str, subStringLength) {
if (str.length < subStringLength) {
return [];
}
var substrings = [];
if (str.length === subStringLength) {
return substrings.push(str);
}
for (var i = 0; i < (str.length - subStringLength); i++) {
substrings.push(str.substring(i, i + subStringLength));
}
return substrings;
}
function findLargestPalindrome(str) {
if (isPlaindrome(str)) {
return str;
}
var length = str.length - 1;
for (var i = length; i >= 2; i--) {
var subStrings = getAllPossibleSubstrings(str, i);
for (var j = 0; j < subStrings.length; j++) {
if (isPlaindrome(subStrings[j])) {
return subStrings[j];
}
}
}
return '';
}
Approach:
-Have 3 pointer (or three char var in case Java String) prev, char and next
-Move pointer one by one and check whether prev and next are same
-In case prev and next are not same keep moving
-In case prev and next are same, save char in MaxPalindromeMid, check prev's prev and next's next and keep checking, increase counter util not same not occurs
-Resume moving step by step and check all the palindrome and update counter and MaxPalindromeMid only in case got bigger then prev palindrome.
//l and r are centers of palindrom
//returns max palindrom size arouns l and r centers
//let call palindrom centers index's around palindrom center
{
int sz=0;
int rr=r;
int ll=l;
if(s.length()==0)return 0;
while(ll>=0&&rr<s.size())
{
if(s[l]==s[r])sz++;
else break;
++rr;--ll;
}
if(r-l==1)return 2*sz;
else if(r-l==2)return 2*sz+1;
else return 0;//error case
}
std::string largest_palindrom(std::string s)
{
int max_sz=0;
int c=0;
for(int i=0;i<s.length()+1;++i)
{
int e=max_palindrom(s,i-1,i);//for even size palindroms
int o=max_palindrom(s,i-1,i+1);//for odd size palindroms
if(std::max(o,e)>max_sz)
{
max_sz=std::max(o,e);
c=i;
}
}
//sz is a largest palindrom size
//but I return largest palindrom
return s.substr(c-max_sz/2,max_sz);
}
in worst case it works in O(n^2) time
but average time is O(n)
use O(1) memory
algorithm is simply don't use hard techniques
In java:
import java.lang.*;
class HelloWorld{
public static int size(String str){
for(int j = 0;j < str.length() / 2;j++){
if(str.charAt(j) != str.charAt(str.length() - 1 - j)) return 0;
}
return str.length();
}
public static void main(String []args){
String str = "anna atoyota atoyota !";
int size = 0;
int count = 0;
for(int i = 0;i < str.length();i++){
if(str.charAt(i) == ' '){
if(size(str.substring(count, i)) > size) size = size(str.substring(count, i));
//System.out.println(str.substring(count, i));
count = i + 1;
}
}
System.out.println(size);
}
}
Here is dynamic programming solution...
Let R[i][j] = {0} ... stores the computation results of (i, j) frame.
Let is_pal(A, i, j): returns palindrome length of substring A[i...j], if its a palindrome, 0 otherwise.
mpal(A, i, j) {
if(R[i][j])
return R[i][j];
else
return (R[i][j] = max{mpal(A, i+1, j-1), mpal(A, i, j-1), mpal(A, i+1, j), is_pal(A, i, j)});
}
(A, i,j):
java code to print maximum palindrome
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class largetpalindrome {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
String path = "C:\\Users\\Administrator\\Desktop\\test\\test\\src\\input.txt";
FileReader fr = new FileReader(path);
BufferedReader br = new BufferedReader(fr);
String line;
// input array one
line = br.readLine();
char[] c = line.toCharArray();
int max=0,result=0;
boolean sucess=true;
for(int i = 1;i<c.length-1;i++)
{
int pre=i-1,next=i+1;
while(sucess){
if(c[pre]==c[next])
{
max++;
if(pre!=0)
{
--pre;
}else
break;
if(next!=(c.length-1))
++next;
else
break;
}
else
sucess=false;
}
sucess =true;
if(result<max)
result=max;
max=0;
}
result=result*2+1;
System.out.print(result+" ");
}
}
This solution provides algorithm complexity of O(N) and space complexity of O(1). The reasoning, code and test are explained here: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-find.html
Pseudo-code
1. If the string is empty, then return -1.
2. If the string has only one character, then return 1.
4. If the string has two characters,
return 2, if two characters are equal,
return 1, if they are not
5. Assign tempIndex = 0; curIndex = 1; foundPalindrome = false and palindromeLength = 1
6. If str[curIndex] is equal to str[curIndex - 1], then set tempIndex = curIndex -1 and foundPalindrome = true. Increment curIndex until str[curIndex] is equal to str[tempIndex] and str[curIndex + 1] is not euqal to str[tempIndex], Go to Step 8,
7. If str[curIndex] is equal to str[curInex - 2] (only if curIndex - 2 is valid index), then set tempIndex = curIndex - 2 and foundPalindrome = true.
8. Increment curIndex anyway, If str[curIndex] is euqal to str[tempIndex - 1] (only if tempIndex -1 is a valid Index), decrement tempIndex.
9. Repeat Step 8 until
9. 1 curIndex reaches the end of str: then save the result if (curIndex - tempIndex) > palindromeLength and return.
9.2 tempIndex - 1 reaches beyond the start of str or str[curIndex] != str[tempIndex - 1]: then clear foundPalindrome and save the result if (curIndex - tempIndex) > palindromeLength. Then go to Step 6.
#include <string>
struct PalindromeInString
{
int pos; // start position in string
int len; // length of palindrome
};
PalindromeInString FindLargestPalindromeInString(const std::string& str)
{
if (str.empty()) {
return PalindromeInString{ -1, -1 };
}
if (str.length() == 1) {
return PalindromeInString{ 0, 1 };
}
if (str.length() == 2) {
if (str[0] == str[1]) {
return PalindromeInString{ 0, 2 };
}
else {
return PalindromeInString{ 0, 1 };
}
}
PalindromeInString result = { 0, 1 };
bool found = false;
size_t tempIndex;
size_t curIndex;
for (tempIndex = 0, curIndex = 1; curIndex < str.length(); ++curIndex) {
if (!found) {
if (str[curIndex] == str[curIndex - 1]) {
// Step 6
found = true;
tempIndex = curIndex - 1;
while ((curIndex + 1) < str.length()) {
if (str[curIndex + 1] != str[tempIndex]) {
break;
}
else {
++curIndex;
}
}
}
else if (curIndex > 1 && str[curIndex] == str[curIndex - 2]) {
// Step 7
found = true;
tempIndex = curIndex - 2;
}
else {
continue;
}
}
else {
// Step 9
if (tempIndex > 0 && str[curIndex] == str[tempIndex - 1]) {
--tempIndex;
}
else {
found = false;
// save the palindrome with max length found so far
if (result.len < (curIndex - tempIndex)) {
result = { tempIndex, curIndex - tempIndex };
}
}
}
}
if (found && result.len < (curIndex - tempIndex)) {
result = { tempIndex, curIndex - tempIndex };
}
return result;
}
Idea is simple: find largest odd palindrome and even one and then find largest among two.
size_t StrLen(char *s)
{
size_t length = 0;
if (s)
{
for (; *s; length++, s++);
}
return length;
}
bool FindLongestPalindrome(char *s, int *piBegin, int *piEnd)
{
bool fFound = false;
size_t length = 0;
int i = -1;
int j = -1;
if (s && piBegin && piEnd)
{
length = StrLen(s);
*piEnd = 0;
*piBegin = 1;
// find longest odd palindrome
for (int k = 0; k < length; k++)
{
i = k;
j = k;
while (i >= 0 && j < length)
{
if (s[i] != s[j])
{
break;
}
else
{
if (j - i > *piEnd - *piBegin)
{
fFound = true;
*piEnd = j;
*piBegin = i;
}
i--;
j++;
}
}
}
// find longest even palindrome
for (int k = 0; k < length - 1; k++)
{
i = k;
j = k + 1;
while (i >= 0 && j < length)
{
if (s[i] != s[j])
{
break;
}
else
{
if (j - i > *piEnd - *piBegin)
{
fFound = true;
*piEnd = j;
*piBegin = i;
}
i--;
j++;
}
}
}
}
return fFound;
}
I haven't coded it but I have a approach. Get to the middle of string. Check its left index of middle and right one. If both are same , then keep on incrementing right index and decrement left index. Once difference is found , we have the currently available longest palindrome string. Pass this length recursively for two sub strings - Left and Right.
As per static analysis, it's complexity will be O(nlogn)..
Thoughts....
class Program
{
static void Main(string[] args)
{
string data="knammans";
bool check;
int[] arr=new int[data.Length];
int counter = 0;
for (int i = 0; i < data.Length-2;++i )
{
for(int j=i+1;j<data.Length-1;++j)
{
if(data[i]==data[j])
{
check = palindrome(data.Substring(i, j - i + 1));
if(check)
{
arr[counter++] = j - i + 1;
}
}
}
}
Console.WriteLine("max substring is:{0}",arr.Max());
Console.Read();
}
static public bool palindrome(string data)
{
int i, f;
i = 0; f = data.Length - 1;
while(i<f)
{
if (data[i] == data[f])
{
i++;
f--;
continue;
}
else
return false;
}
return true;
}
}
public static int findLargestPalindrome(String text){
String[] strings = text.split(" ");
int largest = 0;
for (int i = 0; i < strings.length; i++) {
if (isPalindrome(strings[i])) {
if (largest<strings[i].length()) {
largest = strings[i].length();
}
}
}
return largest;
}
public static boolean isPalindrome(String s){
int i=0,j=s.length()-1;
boolean isPalindrome = true;
while (i<j) {
if (s.charAt(i) != s.charAt(j)) {
isPalindrome = false;
break;
}
i++;j--;
}
return isPalindrome;
}
just use mancher algorithm..complexity O(n)
- @@@@@@@ November 16, 2014