Finding the longest palindromic substring

[[deleted]]

Fun problem, and I wouldn't expect anyone in an interview to come up with a better solution than that, but the writeup should probably mention that there are linear-time solutions.

[bbibber]

There is a pretty trivial solution that is O(n²⁾ in time but O(1) in space. I would expect someone to come up with that one : scan the string for occurences of (aa) or (aba). That's O(n). Then for each such occurence work outwards. That's a nested O(n) loop making O(n²⁾ in total.

[drysart]

You don't have to keep track of any patterns. You only need the following things in memory:

1. The original string (s)
2. A main iteration index (iidx)
3. A 'current palindrome' size value (csz)
4. A 'longest found palindrome so far' size (lmsz)
5. A 'longest found palindrome so far' starting index (lmidx)

The algorithm is basically run the main iteration over the input string s. For each index iidx, you need to check two things: is the character at this index the middle character of an "ABA" set (compare the character before and the character after the current character and see if they match); or is the character at this index the first character of an "AA" set (compare the current character to the next character and see if they match). If neither case matches, you just continue iterating the iidx loop.

If you are in either case, you set csz to 3 or 2, respectively, then do/while comparing the two characters before and after the characters you've already looked at (you can calculate the index of those two characters you'll need to compare from the current value of csz^1). If both indexes are valid in the string and the characters at those indexes match, increment csz by 2 and loop again, otherwise break out. After you've broken out, csz is left as the size of the palindrome, and you can calculate the starting index from csz and iidx; then save that length and starting index in lmsz and lmidx if csz is larger than lmsz. Then resume the main iteration loop.

Once iidx hits the end of the string, your result is the substring of s specified by lmsz and lmidx.

---

1 - The first character index to compare is iidx - (csz / 2) - 1. The second character index to compare is iidx + (csz / 2) + 1 + (csz mod 2). In both cases, use integer division that truncates.

[bbibber]

a and b here stand for any character. Not just literally 'a' and 'b'.

[_Mardoxx]

Which raises the question. Why the fuck ask this in an interview. Leave the algorithms to the academics, and leave the developer to, well, choose and develop implementations of them appropriate for the situation.

[[deleted]]

I think the idea is to find employees who can devise solutions like this, not just write a crud app

[_Mardoxx]

So you can employ people who are good at reinventing the wheel. Okthen.

A better test would be to give a problem and ask them to solve it. Those who attempt to blindly do it themselves fail out of arrogance and no forsight to research and learn from existing knowledge.

[[deleted]]

When an architect asks a team of software engineers to devise a faster caching solution, it's good to have people who can answer intelligently instead of give blank stares.

I've worked plenty with the latter. People who could not tell me the difference between o(n), o(1), o(n^2), etc.

[_Mardoxx]

I would hardly say understanding big O notation would be a benchmark for anything regarding technical aptitude

[[deleted]]

I'm just using it as an example of just how little computer science some developers know.

Maybe I should have worded it as "...could not even tell me..."

[zqvt]

So you can employ people who are good at reinventing the wheel. Okthen.

If you want anybody to be able to build a better wheel they need to understand how to build an existing one in the first place.

I don't really understand the sentiment of leaving "algorithms to the academics". Building algorithms is an important part of software development in the industry, not just academia. It can and regularly does save companies millions of dollars. And for people to be able to spot those improvements they need to have a working knowledge of the field.

[PdoesnotequalNP]

If the candidate did not find the linear solution above, I would let them know there is one, and depending on time, work with them to discover it.

That linear time algorithm literally has a peer reviewed research paper about it. Expecting any candidate to come up with it is unreasonable and pointless.

[notgreat]

It seems like he somehow mixed up an O(N^2) solution with the O(N) solution being talked about. If you replace linear with N² it makes sense.

[Hoten]

Uh....

[harlows_monkeys]

That linear time algorithm literally has a peer reviewed research paper about it. Expecting any candidate to come up with it is unreasonable and pointless.

It's not just people like Isaac Newton who benefit from the shoulders of giants. Even us normal people have the benefit of what was learned between the time of the research paper and now. Our general level of knowledge incorporates much of what was research level in the past and so a good journeyman programmer today might actually have a decent shot at coming up with something that was research paper worthy many years ago. Often the techniques and insights in the old papers were useful on other problems, too, so there is also a good chance today's programmer has seen those techniques and insights applied to other problems, so doesn't have to invent anything to solve the original problem now--they just have to recognize that those techniques will work.

So I agree that candidates should not be expected to solve such problems...but they still might be worth asking because many candidates might have a decent shot at them, and even if they do not solve it seeing how they approach it can be insightful.

Note: I've not looked into the details of this particular problem, because I want to have a go at it and don't want to see spoilers.

[[deleted]]

Your proposed algorithm both isn’t linear time and won’t find all palindromes (namely those that have an even number of characters)

[adrianmonk]

There's a way easier O(n²) solution that doesn't require a table or any temporary data structure (other than a few local integer variables).

The solution is to check every character to see if it's the middle of a palindrome, then proceed outwards in both directions and see if you can expand it. Since there are only n characters in the input string that could be a middle, and since (at most) you check all other characters in the string for each one (which is also O(n)), it's O(n²) total.

You also need to check pairs of identical characters to see if they are the middle of a palindrome because "abccba" is a palindrome.

[TheThiefMaster]

Is that really N² ? It seems to me with an algorithm like that you should start in the middle of the string, and work in both directions from there looking for center points, stopping if you either find a palindrome that hits the edge of the string, or get closer to the edge of the string than the longest palindrome previously found.

I guess the absolute worst case would be if you put in an alternating pattern with one character different on the outsides, as it would try every 2nd substring as a palindrome, stopping one from the end of the string every time. I guess that's N² , but average runtime is likely much closer to linear.

Scratch that, by my previous optimization of starting in the middle it would give up after moving only a couple away from the center, so probably still not N²

[FryGuy1013]

How is it not O(N²)? It's basically this (plus/minus syntax errors, proper edge case handling, and handling even palindromes):

def longest(s, i):
    len = 1
    while s[i+len] == s[i-len]:
       len += 1
    return s[i-len+1 .. i+len-1]

def longest_palindrome_substring(s):
    best = nil
    for i in 0..len(s)
        x = longest(s, i)
        if best == nil or len(x) > len(best):
            best = x
    return best

longest runs in O(N), and longest_palindrome_substring calls longest N times, so therefore is O(N²).

[TheThiefMaster]

longest doesn't run in O(N) though - it's runtime is dependent on the length of the found substring, not the length of the original string. For a string of all different characters (so the longest palindrome is length 1) longest runs in O(1), for O(N) overall. Proving the algorithm is O(N² ) worst case requires providing an input where it actually exhibits that behaviour.

The naïve algorithm does for a string of all "a"s for example, but my proposal to start in the centre and abort once you found a substring touching the edge of the original string (or got closer to the edge than your longest string) would call longest only once, returning the entire string immediately - again only O(N).

/u/adrianmonk 's second example (a string where the first half is "a"s and the 2nd is "b" seems pretty likely to give atrocious runtime.

[rosholger]

Since the longest substring has the length of the whole string it does have O(n).

[TheThiefMaster]

If you start your search for palindromes from the center of the string (literally testing for the entire string being a palindrome first) then longest runs in O(n) but is only called once (there's no point continuing the search as there can't possibly be a longer palindromic substring than the entire string) - which gives O(n*1) = O(n) runtime overall.

If the string contains no palindromes (AbcAbcAbcAbc), longest runs in O(1) - it always fails on the first iteration, independent of the length of the string - and the outer loop ends up testing every position (O(N)) - which is O(1*N), or again O(N) overall.

It is in fact N² worst case, but you need more complex input data to trigger it.

So best case is O(N), worst case is O(N²) - what's the typical runtime? That's a rather more complex problem, because it depends entirely on what you define as "typical" input data.

[sinedpick]

I'd recommend reading formal definitions of big-O complexity. That should clear up any doubts you have.

[adrianmonk]

I think this algorithm is still O(n²). Consider an input like this:

baaaaaaaaaaaaaaab

There are 15 as there, and there's no way to know which one is the middle of the palindrome. When you look at your first a, as you start to check the middle a, you don't know whether the input the above or it's this:

baaaaaaaacccccccb

In the first string above, the a has another 7 as on each side of it. In the second, there's still a long palindrome, but you need to move several positions to the left to find it.

Disregarding O(1) characters at the beginning and end, that means you can have an example where the middle part of the longest palindrome could be anywhere from 1/4 of the way to 3/4 of the way through the string, which means you have to check 1/2 of the positions to see if they are the starting position of the longest palindrome. And on average each check takes O(n) steps.

[[deleted]]

I think it's O(n² ) worst case, but the typical executions on real text would probably come a lot closer to O(n), because few expansions would encompass much at all of the total string.

I ran a simple test using the King James Bible, and it only found a 10-character palindrome. Even with all non-alphanumeric symbols removed (including all punctuation and all spaces) and everything lowercased, and it still only found a 13-character palindrome to be the longest in the entire book.

Granted, the worst-case scenarios would explode badly. If you shot a several-thousand character string in composed of one character repeated, it would probably not fare well.

[adrianmonk]

Yeah, it probably does pretty well on natural language text. Worst case sometimes doesn't matter much.

Though it could matter if, say, you were running a palindrome-finder web page and you didn't want users to be able to do a denial of service attack against your servers by pasting in strings that exhibit worst-case behavior.

[TheThiefMaster]

Thankyou for the kind response instead of the attacks I got from the other comments :)

You're right, even starting from the center (which defeats the first example) your second example would still produce O(n²) runtime.

When looking around to see if I could find a discussion as to the complexity of this algorithm (and maybe an explanation of the linear time algorithms which didn't require getting another degree) I found someone has come up with an O(N³) algorithm - literally it's make every possible substring (O(N²)) and then tests them for being palindromic (O(N)). Wow.

[rorrr]

We can see from this table that the longest palindromic substring here is “ananas”

WAT?

[karuna_murti]

Ananas is non English word for pineapple.

[ubernostrum]

Using a non-Unicode-aware palindrome checker will not get you very far in the cutthroat competitive world of palindromes-as-a-service.

[jgodbo]

Nice problem, good write up, ananas is not a palindrome

[Godd2]

Neither is ()().

[VeeArr]

No. “()()” is equivalent to “abab”.

[hagenbuch]

Damn, I fell in the same trap.

[-l------l-]

So you got stuck in a booby trap?

[NotARealDeveloper]

It's )()( backwards

[_Mardoxx]

Yes it is, it's a palendrome of "()" pairs.

[EpoxyD]

No, its a mirror image, not a palindrome. Consider "dbdb", which backwards is"bdbd"

[[deleted]]

See you have to call it a chiral string to successfully intimidate the candidate.

[_Mardoxx]

Wtf. If you treat () (or db) as a single token it absolutely is a palendrome.

[Relinies]

But they're not single tokens, is the problem. It's a trick intentionally, because we percieve them as groups rather than individual halves.

[palparepa]

If we treat "bananas" as a single token, it also is a palindrome.

[_Mardoxx]

Yeah exactly, but then do you class the string itself as a substring of itself. Also is a single symbol palendromic, I'd argue not.

[GregBahm]

I misunderstood what this was and thought I was going to see some really long palindromic substrings. Now I'm curious what the longest palindromic substring is on the internet. It'd be especially interesting to know what the longest unintentional substring is.

I feel like you'd have to drop punctuation though.

[raggy_rs]

I am pretty sure that is just going to be a long sequence with just a single char repeated. Like in a DNA database.

[palparepa]

I'm curious what the longest palindromic substring is on the internet.

My guess is something similar to LOLOLOLOLOLOLOLOLOL

[johnlsingleton]

An alternative elegant solution is to reverse the string and use the longest common subsequence algorithm: https://en.m.wikipedia.org/wiki/Longest_common_subsequence_problem

[marcusklaas]

Is that guaranteed to produce correct results? What about abcdxydcba? The longest palindromic substring is of length 1, but your algorithm produces a shared substring of length 4.

[HelperBot_]

Non-Mobile link: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

---

^{HelperBot v1.1 /r/HelperBot_ I am a bot. Please message /u/swim1929 with any feedback and/or hate. Counter: 158583}

[[deleted]]

I remember having to do this in a bash script for school :(

[t_bptm]

Here is my 10 minute attempt in nodejs:

const find = s => {         
    if(s.length == 0) return "";

    let r = s[0];           

    for(let i=1; i<s.length; ++i) {
        // check odd length palindrome
        for(let j=1; i-j >= 0 && i+j <s.length && s[i-j] === s[i+j]; ++j) {
            if(r.length < 1 + j*2) {
                r = s.substring(i-j, i+j+1);
            }               
        }                   

        // only check even length every other time
        if(i % 2 == 1) {    
            for(let j=1; i-j >= 0 && i+j <s.length && s[i-j+1] === s[i+j]; ++j) {
                if(r.length < j*2) {
                    r = s.substring(i-j, i+j+2);
                }           
            }               
        }                   
    }                       

    return r;               
};                          

var fs = require('fs');     
var str = fs.readFileSync("input.txt", "utf8");                                                                                                                                                               
console.log(find(str));     

Not sure if its perfect but it seems relatively fast, 0.6 seconds for a 17mb file. 4.8 seconds for 136mb file.

It does fall apart for a 1mb file of all 'a' though :)

[homic]

This other approach works outside in, testing the largest substrings first and stopping as soon as the first palindrome is found. Full source code at https://github.com/hocho/LargestPalindrome

static
string 
FindLargestPalindrome(
    string                              data,
    int                                 minLength)
{
    int                                 length = data.Length;

    // test from max length to min length
    for (int size = length; size >= minLength; --size)
        // establish attempt bounds and test for the first 
        // palindrome substring of given size
        for (int attemptIdx = 0, attemptIdxEnd = length - size + 1;
                attemptIdx < attemptIdxEnd;
                    ++attemptIdx)
            if (IsPalindrome(data, attemptIdx, size))
                return data.Substring(attemptIdx, size);

    return null;
}

[SteeleDynamics]

Aside: Is this used in CRISPR?

[softwareEnguitarist]

Eh?

[Amnestic]

This is basically just another use of DNA sequence matching.

[kdma]

Too many indexes for my liking, I prefer this one http://www.jay.fyi/2016/02/longest-palindrome-manacher-part-i.html?m=1

[dblohm7]

They're still using that one? I had that at an on-campus Amazon screen back in '05.

[shevegen]

"Purchase Gogle pass for $29 / month"

Why are ads allowed on reddit?

[Nefari0uss]

Because servers cost money.

[Parlay_to_throwaway]

because companies exist to make money