CODEWITHSUNDEEP
algorithmpalindrome
Kan
Kan

Reputation: 113

How to detect the first occurrence of palindrome

Suppose you are reading from a character stream, the function should return when you have read the first occurrence of palindrome.

The length of the palindrome should be even number.

The requirement of the time complexity is O(N).

Example:

Upvotes: 9

Views: 1637

Answers (8)

gcbenison
gcbenison

Reputation: 11963

This solution (in Haskell) relies on the observation that an even-length palindrome contains a repeated character at its center. As we read characters from the input stream, we test for such pairs and when one is found, we seed a new candidate answer. For each candidate palindrome we also keep a list of "characters remaining to be matched" and as each new character is read, we match it against this list - without a match, the candidate is discarded. When the match list is null, the solution has been found. Note that though each candidate maintains its own match list, these are all just suffixes of the same list, so in Haskell these will all share space and collectively not take up more than O(n) space even when there are many candidates.

In the best case where there is only one paired character at the center of the answer and hence no "false positive" candidates, time complexity is O(n) - each character is examined no more than twice. In the case of an input string with many false starts i.e. "abbbbbbbbbbbba" I am not sure of the time complexity - it's probably no longer O(n) but it is better than O(n^2) because no candidate is alive for longer than min(k, n-k) where k is the position of the center of the candidate.

filter_map::(a -> Maybe a)->[a]->[a]
filter_map op = foldr (maybeCons . op) []
  where maybeCons Nothing  ys = ys
        maybeCons (Just y) ys = y:ys

-- Return the first prefix of the input argument that
-- is an even-length palindrome.
prefix_palindrome::(Eq a)=>[a]->[a]
prefix_palindrome (x:xs) = search [x] [] xs
  where search seen ([]:_) _ = seen
        search (s:seen) candidates (x:xs) | x == s = search seen' (candidates' ++ [seen]) xs
                                          | otherwise = search seen' candidates' xs
          where seen' = (x:s:seen)
                candidates' = filter_map extend candidates
                              where extend (c:cs) | c == x = Just cs
                                                  | otherwise = Nothing

Upvotes: 0

Victor Sorokin
Victor Sorokin

Reputation: 11996

Ok, since my 1st answer has O(n^2) time complexity, here's another, with O(n), as requested.

class PalindromeDetector {
    private static class DetectorImpl {
        int firstHalfSum, secondHalfSum;
        int size = 0, tensPower = 1;

        boolean add(int v) {
            if (size % 2 == 1) {
                firstHalfSum = firstHalfSum + (secondHalfSum / tensPower) * tensPower;
                secondHalfSum = (secondHalfSum % tensPower) * 10 + v;
                if (firstHalfSum == secondHalfSum)
                    return true;
            } else {
                secondHalfSum = secondHalfSum * 10 + v;
            }

            size ++;
            if (size % 2 == 0)
                tensPower *= 10;

            return false;
        }
    }

    static boolean isPalindrome(String s) {
        if (s == null || s.length() == 0)
            return false;

        int val = Integer.parseInt(s);
        int tensPower = s.length() == 1 ? 1 : (int) (Math.pow(10, s.length() - 1));
        DetectorImpl detector = new DetectorImpl();
        while (tensPower > 0) {
            int digit = val / tensPower;
            if (detector.add(digit))
                return true;

            val = val % tensPower;
            tensPower /= 10;
        }

        return false;
    }
}

And here's unit test:

@Test
public void test() {
    assertFalse(PalindromeDetector.isPalindrome("4113"));
    assertTrue(PalindromeDetector.isPalindrome("3443"));
    assertTrue(PalindromeDetector.isPalindrome("473374"));
    assertTrue(PalindromeDetector.isPalindrome("413314"));
}

Answer assumes that input consists of decimal digits, but can be easily expanded for alphanumeric input (just assume that English alphabet + 10 digits give us numeric system over base 36).

Upvotes: 0

Victor Sorokin
Victor Sorokin

Reputation: 11996

Here's my take. It scans accumulated string on every new symbol from the current middle of the string, so it will fail fast if current string is not palindrome.

class PalindromeDetector {
    private static class DetectorImpl {
        final ArrayList<Character> string = new ArrayList<Character>(32);

        boolean addSymbol(char symbol) {
            string.add(symbol);
            return check();
        }

        private boolean check() {
            if (string.size() < 2)
                return false;

            int lowBound = string.size() / 2 - 1;
            int hiBound = lowBound + 1;
            while (lowBound >= 0 && string.get(lowBound) == string.get(hiBound)) {
                lowBound --; hiBound ++;
            }
            return lowBound == -1;
        }
    }

    static boolean isPalindrome(String s) {
        DetectorImpl detector = new DetectorImpl();
        int index = 0;
        while (index < s.length())
            if (detector.addSymbol(s.charAt(index++)))
                return true;
        return false;
    }
}

Here's unit test for the code:

@Test
public void test() {
    assertFalse(PalindromeDetector.isPalindrome("4"));
    assertTrue(PalindromeDetector.isPalindrome("44"));

    assertFalse(PalindromeDetector.isPalindrome("4343"));
    assertTrue(PalindromeDetector.isPalindrome("4334"));

    assertFalse(PalindromeDetector.isPalindrome("41331"));
    assertTrue(PalindromeDetector.isPalindrome("413314"));
}

Upvotes: 0

Sandeep
Sandeep

Reputation: 7334

How about using Hashset?

lets say the input stream is 1221.

Hashset = empty;

if(hashset does not contain the inputelement)
{
   add to hashset. // 12 will be in the hashset. //413 for your example.
}

else
{
  delete from Hashset. // First deletes 2 and then 1. // First deletes 3, then 1 then 4.

  if(hashset is empty)
    return true; //Hashset is empty. return true.
}

Upvotes: 0

Pinch
Pinch

Reputation: 2888

One approximate solution that should be running in linear time O(n) in most cases is to use rolling hash.

You keep track of the hash of the string and its reverse. Every time you read a new character, you could update the two hash values in O(1). Then you compare the two hashes, if they are equal, then you compare the string and its reserve. If this is also equal, exits and you got a palindrome.

For example one very simple rolling hash function is hash(ck c(k-1).. c0) = (p^k*ck + p^(k - 1) * c(k - 1) + ... + c0) mod m where p is an odd prime.

So start with:

p = 17 // or your lucky prime number
m = 10^9 // ...
hash = 0
hash_rev = 0
str = ''
str_rev = ''
p_pow = 1    

while True
    read c
    append c to str
    prepend c to str_rev
    hash = (hash * p + c) mod m
    hash_rev = (hash_rev + p_pow * c) mod m
    p_pow = p_pow * p
    if hash == hash_rev
         if str == str_rev
             found str to be the first palindrome

To make it even faster, you can decleare your hash and hash_rev to be 32 bit integer and pick m = 2^32. Then you can ignore the (mod m) operation.

Upvotes: 3

kilotaras
kilotaras

Reputation: 1419

What you need is a slight modification of Manacher's Algorithm. It allows you to find all palindromes in a string in linear time. The thing about algorithm it, that it actually proceeds from left, to right, "using" new chars when needed. The modification needed, is that you need to read new character, only when you try to access it.
Stop, if you found palindrome, that goes all way back to the beginning of the stream.

Upvotes: 3

jb.
jb.

Reputation: 10341

This (untested C#) code will do it, but I think it might be O(n^2). Can anyone confirm/deny that please?

main()
{
    string str = "";
    char c1;
    char c2;

    while(true)
    {
        //has to be even, always get two chars at a time
        c1 = GetCharFromStream();
        c2 = GetCharFromStream();
        str += c1 + c2;
        if(isPalindrome(str))
        {
            Console.WriteLine(str);
            return;
        }
    }
}

bool isPalindrome(string str)
{
    if (str.Length % 2 != 0)
        throw new InvalidArgumentException("str");

    int first = 0;
    int last = str.Length - 1;

    while(first <= last)
    {
        if(str[first] != str[last])
            return false;

        first++;
        last--;
    }

    return true;
}

Upvotes: 0

oksayt
oksayt

Reputation: 4365

Return when you read the first character, that's a one-letter palindrome.

Upvotes: 3

Related Questions