To optimal the second function

Question

srihari · Accepted Answer

you can do this in N*LogN ,using a divide and conquer approach
each time you divide, from the middle go outwards and harness all palindromes

srihari · Answer

code for this

using System;
using System.Collections.Generic;

class PalindromeFinder
{
    private HashSet palindromeSet;
    
    public PalindromeFinder() {
        palindromeSet = new HashSet();
    }
    
    public HashSet GetAllPalindromes(String str) {
        GetAllPalindromesR(str, 0, str.Length-1);
        return palindromeSet;
    }
    
    private void GetAllPalindromesR(String str, int start, int end) {
        //base cases
        if(start==end) {
            AddToSet(str, start, end);
            return;
        }
        
        
        int middle = start + (end-start)/2;
        
        GetAllPalindromesR(str, start, middle);
        GetAllPalindromesR(str, middle+1, end);
        
        if((end-start+1)%2 != 0) {
            //odd case
            GetPalindromesAround(str, middle, start, end);
        } else {
            //even case
            GetPalindromesAround(str, -1, start, end);
            GetPalindromesAround(str, middle, start, end);
            GetPalindromesAround(str, middle+1, start, end);
        }
    }
    
    private void AddToSet(String str, int start, int end) {
        String substring = str.Substring(start,end-start+1);
        if(!palindromeSet.Contains(substring)) {
            palindromeSet.Add(substring);
        }
    }
    
    public void GetPalindromesAround(String str, int pos, int first, int last) {
        //odd case
        int start = pos-1;
        int end = pos+1;


        //even case
        if(pos == -1) {
            start = (last-first)/2;
            end = start + 1;
        }
        
        while(start >= first && end <= last) {
            if(str[start]==str[end]) {
                AddToSet(str, start, end);
                start--;
                end++;
            } else {
                break;
            }
        }
    }
    
    static void Main(string[] args)
    {
        PalindromeFinder pFinder = new PalindromeFinder();
        foreach (String palindrome in pFinder.GetAllPalindromes("malayalam"))
        {
            Console.WriteLine(palindrome);
        }
    }
}

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches