Algorithm to find the three longest unique palindromes in a string

Question

Using C#, write an algorithm to find the three longest unique palindromes in a string. For the three longest palindromes, report the palindrome text, start index and length in descending order of length. For example, the output for string,

sqrrqabccbatudefggfedvwhijkllkjihxymnnmzpop

should be:

Text: hijkllkjih, Index: 23, Length: 10 Text: defggfed, Index: 13, Length: 8 Text: abccba, Index: 5 Length: 6

Now I got to the part where I can write out the palindromes and its length but I have a problem with the index. Need help on how to include the index of the palindrome and how to get unique lengths

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string inputString = "sqrrqabccbatudefggfedvwhijkllkjihxymnnmzpop";
            string currentStr = string.Empty;
            List<string> listOfPalindromes = new List<string>();

            char[] inputStrArr = inputString.ToCharArray();

            for (int i = 0; i < inputStrArr.Length; i++)
            {
                for (int j = i+1; j < inputStrArr.Length; j++)
                {
                    currentStr = inputString.Substring(i, j - i + 1);

                    if (IsPalindrome(currentStr))
                    {
                        listOfPalindromes.Add(currentStr);
                    }
                }
            }

            var longest = (from str in listOfPalindromes
                           orderby str.Length descending
                           select str).Take(3);

            foreach (var item in longest)
            {
                Console.WriteLine("Text: " + item.ToString() + " Index: " +  + " Length: " + item.Length.ToString());
            }
        }

        private static bool IsPalindrome(String str)
        {
            bool IsPalindrome = true;
            if (str.Length > 0)
            {
                for (int i = 0; i < str.Length / 2; i++)
                {
                    if (str.Substring(i, 1) != str.Substring(str.Length - (i + 1), 1))
                    {
                        IsPalindrome = false;
                    }
                }
            }
            else
            {
                IsPalindrome = false;
            }
            return IsPalindrome;
        }
    }
}

ok now that's out of the way how do I get distinct lengths? can it be done by using DISTINCT or do I need to edit something else?

You have to store additional info regarding found polindrome at the moment you found one. Index would be current `i`. — Sinatr, Sep 17 '14 at 13:38
Regex quick guide: http://msdn.microsoft.com/en-us/library/az24scfc%28v=vs.110%29.aspx — Cullub, Sep 17 '14 at 13:40
Replace str.Substring(i, 1) with str[i]. Comparing chars is much more efficient than comparing strings. And you are using inputStrArr only to get the length. Just use inputString.Length. — Dennis_E, Sep 17 '14 at 13:40
Why would you need distinct lengths? Don't you want to report both palindromes in `"abccbadeffed"` ? — Kris Vandermotten, Sep 17 '14 at 14:07

score 1 · Answer 1 · answered Sep 17 '14 at 13:50

1

You need to store more information when a palindrome is found.

First define a class:

class PalindromeResult
{
    public string Text { get; set; }
    public int Index { get; set; }
}

Then instead of your List<string>, create a list of this class:

List<PalindromeResult> listOfPalindromes = new List<PalindromeResult>();

When a result is found, ad it like this

if (IsPalindrome(currentStr))
{
    listOfPalindromes.Add(new PalindromeResult { Text = currentStr, Index = i});
}

You would have to update your sorting and printing accordingly.

answered Sep 17 '14 at 13:50

Kris Vandermotten

10,111
38
49

Alternatively it's possible to use `Dictionary` instead of list, where `int` is index and `string` would be palindrome. Or use `Tupple<>` (but I dislike `ItemX` properties myself). – Sinatr Sep 17 '14 at 13:57
@Sinatr True. However I like data structures express their intent, and I feel an explicit class does it better than using a dictionary (or a tuple). A dictionary is a mechanism to lookup a value by its key. We're not doing that lookup here. Furthermore, to a beginner programmer, using and sorting a dictionary for this purpose could be confusing. – Kris Vandermotten Sep 17 '14 at 14:00

score 0 · Accepted Answer · answered Sep 17 '14 at 13:39

0

The most optimal solution (as pointed out by Sinatr) would be to store the index of the palindromes as you find them.

You could instead use the IndexOf function to find the index of the first occurrence of a substring within a string.

For example inputString.IndexOf(item) could be used in your Console.WriteLine function.

answered Sep 17 '14 at 13:39

Adam H

1,523
11
21

If you mean to search again in source string, then this is not optimal. – Sinatr Sep 17 '14 at 13:40
@Sinatr true, but the algorithm is not optimal anyway. – Kris Vandermotten Sep 17 '14 at 13:43
Then store the index in the list as well. Create a struct that holds the palindrome and the index. (or use KeyValuePair) – Dennis_E Sep 17 '14 at 13:43
@KrisVandermotten, is [this](http://stackoverflow.com/a/9790916/1997232) one is better? – Sinatr Sep 17 '14 at 13:43
1

What if the same palindrome appears twice in the same string? You would report the same index for both occurences, which would be wrong. – Kris Vandermotten Sep 17 '14 at 13:43
tnx i does the job. maybe if you could help a little bit with the optimizing of the linq query, so as i said i need it to write out unique lengths not repeat the length: 8 twice – Istvan Nadj Sep 17 '14 at 13:49
@Sinatr The function IsPalidrome is not too bad, except for the use of SubString instead of the string indexer. The search algorithm itself is very brute force, and does not eliminate the sort palindrome "bab" in the long "cbabc" one from the search results. - Anyway, that is not what this question is about. – Kris Vandermotten Sep 17 '14 at 13:54
@IstvanNadj You accepted this answer, but it's wrong. Test in on the string `"abcxyzyxdefghixyzyxj"`. – Kris Vandermotten Sep 17 '14 at 14:03

score 0 · Answer 3 · answered Sep 17 '14 at 14:28

Try This

public static bool IsPalindromic(int l)
    {
        IEnumerable<char> forwards = l.ToString().ToCharArray();
        return forwards.SequenceEqual(forwards.Reverse());
    }

    public int LongestPalindrome(List<int> integers)
    {
        int length=0;
        int num;
        foreach (var integer in integers)
        {
            if (integer.ToString().Length > length)
            {
                num = integer;
                length = integer.ToString().Length;
            }
        }
        return num;
    }


    public void  MyFunction(string input)
    {

        var numbers = Regex.Split(input, @"\D+").ToList();
        var allPalindromes = (from value in numbers where !string.IsNullOrEmpty(value) select int.Parse(value) into i where IsPalindromic(i) select i).ToList();
        if (allPalindromes.Count>0)
            Console.WriteLine(LongestPalindrome(allPalindromes));
        else
            Console.WriteLine("Any Palindrome number was found");

    }

you cans mix the 2 two functions to have a beautiful code but i done it like this to simplify.

Algorithm to find the three longest unique palindromes in a string

3 Answers3