0
\$\begingroup\$

I have a list of palindromes

List<string> palindromes = new List<string>() 
{
    hijkllkjih,
    ijkllkji,
    jkllkj,
    kllk,
    ll,
    defggfed,
    efggfe,
    fggf,
    gg,
    abccba, 
    bccb,
    cc,
    qrrq, 
    rr,
    mnnm, 
    nn,
    pop, 
    o,
    s, 
    q,
    r
};

But I want to remove palindromes that are substring of other palindromes. So, the list would become

List<string> palindromes = new List<string>() 
{
    hijkllkjih,
    defggfed,
    abccba, 
    qrrq, 
    mnnm, 
    pop, 
    s, 
    q,
    r
};

To do this I have written the following code

List<int> indexList = new List<int>();
for (int i = 0; i < palindromes.Count; ++i)
{
    if (indexList.Contains(i))
        continue;

    string tmp = palindromes[i];
    for (int j = 0; j < palindromes.Count; ++j)
    {
        if (i == j 
            || indexList.Contains(j) 
            || palindromes[j].Length > palindromes[i].Length)
            continue;

        if (tmp.Contains(palindromes[j]))
            indexList.Add(j);
    }
}

foreach (var index in indexList.OrderByDescending(l => l))
    palindromes.RemoveAt(index);

Can this be improved?

\$\endgroup\$
  • \$\begingroup\$ What is .Sequence? \$\endgroup\$ – t3chb0t Aug 15 '17 at 8:46
  • \$\begingroup\$ Sorry, I tried to make the code a simple as possible by removing the class structure. Now it should make sense... \$\endgroup\$ – MoonKnight Aug 15 '17 at 8:47
  • 3
    \$\begingroup\$ I tried to make the code a simple as possible this is never a good idea because most probably you're going to get answers suggesting things that you already have and you'll answer that you already implemented the idea etc etc, normally a waste of time ;-) so please post your real code. \$\endgroup\$ – t3chb0t Aug 15 '17 at 8:51
  • 4
    \$\begingroup\$ I suppose the expected result you've described is wrong since q is substring of qrrq so must be removed as well as r. \$\endgroup\$ – Maxim Aug 15 '17 at 8:54
  • 1
    \$\begingroup\$ The palindroms are not strings so technically your code is broken. \$\endgroup\$ – t3chb0t Aug 15 '17 at 9:18
3
\$\begingroup\$

You can simplify your code to this:

var palindromesCopy = palindromes.ToList();
palindromes.RemoveAll(x => palindromesCopy.Any(y => x != y &&
                                               y.Contains(x)));

If you want to remove duplicated strings as said by @MoonKnight in comments, just call Distinct on palindromes after removing.

\$\endgroup\$
  • \$\begingroup\$ if I had two entries for "hijkllkjih" say, this would not remove one of them. We need extra logic in this case... \$\endgroup\$ – MoonKnight Aug 15 '17 at 9:21
  • \$\begingroup\$ @MoonKnight I've added the comment in my answer describing "extra logic" :) \$\endgroup\$ – Maxim Aug 15 '17 at 9:28
  • \$\begingroup\$ Worth mentioning, that while this solution is short and simple, it is O(n^2). This looks like an interview/homework question, so you might want to consider more efficient (and less pretty) approaches. \$\endgroup\$ – Nikita B Aug 15 '17 at 10:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.