CareerCup

My algorithm iterates the string from left to right once and try to match the palindromes from inside out, adding the matches to a std::unordered_set (hash set). Written in C++.

Output for "civic":

ivi
v
i
civic
c

Output for "aba":

aba
b
a

Code:

#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>

std::vector<std::string> find_palindromes(const std::string& s, size_t center) {
	std::vector<std::string> palindromes;
    
    // Add current char
    palindromes.emplace_back(1, s[center]);
    
	size_t left = center;
	size_t right = center;
    
	while (left != -1 && right < s.size()) {
		if (s[left] != s[right]) {
            // Try to match one char to the left
            if (left != -1) {
                if (s[left--] == s[right])
                    palindromes.emplace_back(s.substr(left, right - left + 1));
            }
            continue;
        }
        
        // Only add palindrome if length is bigger than 1
        // since we already added it before the loop.
        if (left != right) {
            palindromes.emplace_back(s.substr(left, right - left + 1));
            ++right;
        } else {
            --left;
        }
    }
    
	return palindromes;
}

std::unordered_set<std::string> distinct_palindromes(const std::string& s) {
	if (s.empty())
		return std::unordered_set<std::string>();
    
    std::unordered_set<std::string> result;
	for (size_t i = 0; i < s.size(); ) {
		auto palindromes = find_palindromes(s, i);
		
		// Insert on the set, keeping track of the longest
		size_t longest = 0;
		for (const std::string& p : palindromes) {
			result.insert(p);
			longest = std::max(longest, p.size());
		}
		
		// Skip as much as the longest palindrome found
        if (longest > i)
            i += longest - i;
        else
            ++i;
	}
	
    return result;
}

int main() {
	std::unordered_set<std::string> civic = distinct_palindromes("civic");
	for (const std::string& p : civic) {
		std::cout << p << std::endl;
	}
	std::cout << "--" << std::endl;
	std::unordered_set<std::string> aba = distinct_palindromes("aaaa");
	for (const std::string& p : aba) {
		std::cout << p << std::endl;
	}
}

Not answering the question.

An O(n^2) algorithm is a great response in an interview for this question.

When the interviewer asks for a better algorithm, it does not mean you have done bad. They are looking to see how you think, when trying to come up with a better algo, and are now WANTING or EXPECTING a better algorithm.

Here's a Java code that seems to work :

import java.util.ArrayList;

public class PalindromeFinder {
	
	public static void main (String[] args) {
		PalindromeFinder pf = new PalindromeFinder();
		System.out.println(pf.countDistinctPalindromes("gfdfhweufuefk"));
	}
	
	public int countDistinctPalindromes(String s) {
		for (int i = 0; i < s.length(); ++i) {
			findPalindromes(s, i);
		}
		return found.size();
	}

	private void findPalindromes(String s, int i) {
		int j = i,k = i;
		while ((j >= 0) && (k < s.length()) && (s.charAt(j) == s.charAt(k))) {
			report(s.substring(j--, ++k));
		}
		
		if (i == 0) {
			return;
		}
		
		k = i;
		j = i-1;
		
		while ((j >= 0) && (k < s.length()) && (s.charAt(j) == s.charAt(k))) {
			report(s.substring(j--, ++k));
		}
		
	}
	
	private void report(String s) {
		if (!wasFound(s)) {
			found.add(s);
//			System.out.println(s);
		}
	}
	
	private boolean wasFound(String s) {
		return found.contains(s);
	}

	private ArrayList<String> found = new ArrayList<String>();
}

The printing of all palindromes was commented out, but you can comment it in again.

Its compexity is actually

p^2

where

p

is the number of (not necessarily unique) palindromes in the given string, S, which itself can be

p = O(n^2)

where

n

is the length of S. (worst case achieved when s consist of just one letter, repeating itself), but it's only because I used Java-supplied List, instead of a ballanced tree or even a Trie to keep track of the already found palindromes. This would improve the running time to

O(p log p) =(worst case) O(n^2 log n)

.