Remove a letter to make a palindrome

Question

Problem

Let's say that a word is almost a palindrome if it is possible to remove one of its letters so that the word becomes a palindrome. Your task is to write a program that for a given word determines which letter to remove to get a palindrome.

The shortest code to do this in any programming language wins.

Input

Input consists of a word of lowercase letters from 2 to 1000 characters long.

Output

Output the 1-indexed position (leftmost letter has position 1, the next one has position 2 and so on) of the letter which should be removed. If there are possible choices that lead to the palindrome, output any of those positions. Note that you are required to remove a letter even if the given word is already a palindrome. If the given word is not almost a palindrome, output -1.

---

Examples

The input:

racercar

might produce either of these outputs:

4
5

because removing the 4th letter produces racrcar and removing the 5th letter produces racecar, which are both palindromes.

Also, the input

racecar

can still produce the output

4

because removing the 4th letter to produce raccar is still a palindrome.

The input

golf

should produce the output

-1

because there is no way to remove a single letter to make it a palindrome.

Answer 1

J - 31 25 char

(_1{ ::[1+[:I.1(-:|.)\.])

Largely standard fare for J, so I'll just point out the cool bits.

• The adverb \. is called Outfix. x u\. y removes every infix of length x from y and applies u to the result of each removal. Here, x is 1, y is the input string, and u is (-:|.), a test for whether the string matches its reverse. Hence the result of this application of \. is a list of booleans, 1 in the place of each character whose removal makes the input a palindrome.

• I. creates an list of all the indices (0-origin) from above where there was a 1. Adding 1 with 1+ makes these 1-origin indices. If no indices were 1, the list is empty. Now, we try to take the last element with _1{. (We are allowed to output any of the removable letters!) If this works, we return. However, if the list was empty, there were no elements at all, so { throws a domain error which we catch with :: and return the -1 with [.

Usage (recall that NB. is for comments):

   (_1{ ::[1+[:I.1(-:|.)\.]) 'RACECAR'    NB. remove the E
4
   (_1{ ::[1+[:I.1(-:|.)\.]) 'RAACECAR'   NB. remove an A
3
   (_1{ ::[1+[:I.1(-:|.)\.]) 'RAAACECAR'  NB. no valid removal
_1

Answer 2

Not-PHP Python (73):

[a[:g]+a[g+1:]==(a[:g]+a[g+1:])[::-1] for g in range(len(a))].index(1)

Where a is the string you want to check. This, however, throws an error if you can't turn it in an palindrome. Instead, you could use

try:print [a[:g]+a[g+1:]==(a[:g]+a[g+1:])[::-1] for g in range(len(a))].index(True)
except ValueError:print -1

EDIT: No, wait, it does work!

try: eval("<?php $line = fgets(STDIN); ?>")
except: print [a[:g]+a[g+1:]==(a[:g]+a[g+1:])[::-1] for g in range(len(a))].index(1)

Thanks, this does indeed raise the php-contents of this script by about 25% (that's what you want, right?)

Answer 3

Mathematica, 106 98 87 91 characters

I suppose I'm slightly handicapped by the long function names, but problems like this are quite fun in Mathematica:

f=Tr@Append[Position[c~Drop~{#}&/@Range@Length[c=Characters@#],l_/;l==Reverse@l,{1}],{-1}]&

It throws some warnings, because the l_ pattern also matches all the characters inside, which Reverse can't operate on. But hey, it works!

Somewhat ungolfed:

f[s_] := 
  Append[
    Cases[
      Map[{#, Drop[Characters[s], {# }]} &, Range[StringLength[s]]], 
      {_, l_} /; l == Reverse[l]
    ], 
    {-1}
  ][[1, 1]]

Answer 4

GolfScript, 28 26 characters

:I,,{)I/();\+.-1%=}?-2]0=)

Thanks to Peter for shortening by 2 characters. Try the test cases online:

> "RACECAR" 
4
> "RAACECAR" 
2
> "RAAACECAR" 
-1
> "ABCC1BA" 
5
> "AAAAAA" 
1
> "ABCDE" 
-1
> "" 
-1
> "A" 
1

Answer 5

Japt, 8 bytes

a@jYÉ êS

Try it

a@jYÉ êS     :Implicit input of string
a            :Last 0-based index that returns true (or -1 if none do)
 @           :When passed through the following function as Y
  j          :  Remove the character in U at index
   YÉ        :    Y-1
      êS     :  Is palindrome?

Answer 6

Stax, 8 10 bytes

ú·àA÷¡%5Ñ╙

Run and debug it

This program shows all 1-based indices that can be removed from the string to form a palindrome. And if there are none, it shows -1.

Answer 7

Jelly, 8 bytes

ŒḂ-ƤTȯ-Ḣ

Try it online!

Not overwriting my older answer since it's among my first Jelly answers, but it's still way too embarrassing not to fix. I can't blame myself for not coming up with this exactly since nilad-Ƥ is pretty obscure documentation-wise, but at least JœPẎŒḂɗƇȯ-Ḣ should have been in reach...

  -Ƥ        For each "1-outfix" (remove a single item) of the input,
ŒḂ          is it a palindrome?
    T       List all truthy indices.
     ȯ-     Replace an empty list with -1,
       Ḣ    and return the first element.

Jelly, 17 14 bytes

ŒPṖLÐṀṚŒḂ€TXo-

Try it online!

           X      A random
          T       truthy index
ŒP                from the powerset of the input
  Ṗ               excluding the input
   LÐṀ            and all proper subsequences with non-maximal length
      Ṛ           reversed
       ŒḂ€        with each element replaced with whether or not it's a palindrome,
            o-    or -1.

Since I changed my approach fast enough for the old version not to show up in edit history, it was this: ŒPṚḊŒḂ€TṂ©’<La®o-

Answer 8

05AB1E, 10 9 bytes

ā.Δõs<ǝÂQ

Try it online or verify some more test cases.

Explanation:

ā          # Push a list in the range [1, (implicit) input-length]
 .Δ        # Pop and find the first value in this list which is truthy for:
           # (which will result in -1 if none are truthy)
   õ       #  Push an empty string ""
    s      #  Swap to get the current integer of the find_first-loop
     <     #  Decrease it by 1 because 05AB1E uses 0-based indexing
      ǝ    #  In the (implicit) input-String, replace the character at that index with
           #  the empty string ""
       Â   #  Then bifurcate the string (short for Duplicate & Reverse copy)
        Q  #  And check if the reversed copy is equal to the original string
           #  (so `ÂQ` basically checks if a string is a palindrome)
           # (after which the result is output implicitly)

Answer 9

Rebol (81)

r: -1 repeat i length? s[t: head remove at copy s i if t = reverse copy t[r: i]]r

Example usage in Rebol console:

>> s: "racercar"
== "racercar"

>> r: -1 repeat i length? s[t: head remove at copy s i if t = reverse copy t[r: i]]r
== 5

>> s: "1234"
== "1234"

>> r: -1 repeat i length? s[t: head remove at copy s i if t = reverse copy t[r: i]]r 
== -1

Above returns index of last palindrome found. An alternative solution (85 chars) which returns every palindrome found would be:

collect[repeat i length? s[t: head remove at copy s i if t = reverse copy t[keep i]]]

So for "racercar" this would return list [4 5].

Answer 10

C#, 134 Characters

static int F(string s,int i=0){if(i==s.Length)return-1;var R=s.Remove(i,1);return R.SequenceEqual(R.Reverse())?i+1:F(s,i+1);}

I know I lose :( but it was still fun :D

Readable version:

using System.Linq;

// namespace and class

static int PalindromeCharIndex(string str, int i = 0)
{
    if (i == str.Length) return -1;
    var removed = str.Remove(i, 1);
    return removed.SequenceEqual(removed.Reverse()) 
        ? i+1
        : PalindromeCharIndex(str, i + 1); 
}

Answer 11

Not Python PHP, 85 83 81 bytes

while($argn[$x])$s!=strrev($s=substr_replace($argn,'',$x++,1))?:die("$x");echo-1;

• -2 bytes thanks to @Night2!

Try it online!

Unnecessarily recursive:

PHP, 96 bytes

function f($a,$b='',$d=1){return$a?$c==strrev($c=$b.$e=substr($a,1))?$d:f($e,$b.$a[0],$d+1):-1;}

Try it online!

Answer 12

Brachylog, 20 bytes

l⟧∋.&↻↺↙.b↺↻↙.I↔I∨_1

Try it online!

It was too long

Answer 13

Ruby (61):

(1..s.size+1).find{|i|b=s.dup;b.slice!(i-1);b.reverse==b}||-1

Here, have a ruby solution. It will return the position of the character to remove or -1 if it cannot be done.

I can't help but feel there's improvement to be made with the dup and slice section, but Ruby doesn't appear to have a String method that will remove a character at a specific index and return the new string -__-.

Edited as per comment, ty!

Answer 14

Brachylog, 24 bytes

{l+₁≥.ℕ₂≜&↔⊇ᶠ↖.tT↔T∨0}-₁

Try it online!

Feels way too long.

Could be two bytes shorter if the output could be 2-indexed:

l+₁≥.ℕ₂≜&↔⊇ᶠ↖.tT↔T∨_1

Two earlier and even worse iterations:

ẹ~c₃C⟨hct⟩P↔P∧C;Ȯ⟨kt⟩hl<|∧_1
l>X⁰ℕ≜<.&{iI¬tX⁰∧Ih}ᶠP↔P∨_1

The latter's use of a global variable necessitates a different testing header.

Answer 15

Perl 5 -p, 56 52 bytes

("$`$'"eq reverse"$`$'")&&($\=pos)while/./g}{$\||=-1

Try it online!

Answer 16

Python 3, 681 bytes

from itertools import groupby

def solution(x):
    if len(x) == 1:
        return 1
    lst = [''.join(g) for _, g in groupby(sorted(x))]
    print(lst)
    pal_str_len = 0
    single_elements = False
    odd_elements = False
    for i in lst:
        if len(i)%2 == 0:
            pal_str_len +=len(i)
        elif len(i)%2 == 1:
            if odd_elements:
                pal_str_len +=len(i)-1
            else:
                odd_elements = True
                pal_str_len +=len(i)
        elif len(i) == 1:
            if not odd_elements and not single_elements:
                single_elements = True
                pal_str_len += 1
                
    return len(x)-pal_str_len
x = 'AAABBC'
print(solution(x))

Answer 17

C++, 247 150 bytes

-97 thanks to ceilingcat

TIO Link

#import<map>
int P(std::string s){int i=0,j,q,r=-1;for(;s[i++]*!~r;r=q?r:i)for(auto t=s.substr(j=q=0,i-1)+&s[i];t[j];)q|=t[j]-*(end(t)-++j);return r;}

Test code example :

std::cout << P("RACERCAR") << '\n';

Answer 18

Brachylog, 17 bytes

~cLkʰcP↔P∧Lhl.∨_1

Try it online! (Can be rather slow for inputs that are not almost-palindromes. For faster performance, replace the ~c with ~c₂.)

Explanation

~c                 "Unconcatenate" the string into a list of strings
  L                Call that list of substrings L
   kʰ              Remove the last character from the first substring
     c             Concatenate the list of strings together again
      P            Call that new string P
       ↔           Reverse
        P          Assert that the result is still the same (i.e. P is a palindrome)
         ∧L        Also, going back to the list L
           h       Get its first element
            l      Get its length
             .     This is the output of the predicate
              ∨    Or, if there is no way to satisfy the previous conditions
               _1  Output -1 instead

Answer 19

Haskell, 107 characters:

(x:y)!1=y;(x:y)!n=x:y!(n-1)
main=getLine>>= \s->print$head$filter(\n->s!n==reverse(s!n))[1..length s]++[-1]

As a function (85 characters):

(x:y)!1=y;(x:y)!n=x:y!(n-1)
f s=head$filter(\n->s!n==reverse(s!n))[1..length s]++[-1]

original ungolfed version:

f str = case filter cp [1..length str] of
          x:_ -> x
          _   -> -1
    where cp n = palindrome $ cut n str
          cut (x:xs) 1 = xs
          cut (x:xs) n = x : cut xs (n-1)
          palindrome x = x == reverse x

Answer 20

C# (184 characters)

I admit this is not the best language to do code-golfing...

using System.Linq;class C{static void Main(string[]a){int i=0,r=-1;while(i<a[0].Length){var x=a[0].Remove(i++,1);if(x==new string(x.Reverse().ToArray()))r=i;}System.Console.Write(r);}}

Formatted and commented:

using System.Linq;

class C
{
    static void Main(string[] a)
    {
        int i = 0, r = -1;
        // try all positions
        while (i < a[0].Length)
        {
            // create a string with the i-th character removed
            var x = a[0].Remove(i++, 1);
            // and test if it is a palindrome
            if (x == new string(x.Reverse().ToArray())) r = i;
        }
        Console.Write(r);
    }
}

Answer 21

C# (84 Characters)

int x=0,o=i.Select(c=>i.Remove(x++,1)).Any(s=>s.Reverse().SequenceEqual(s))?x:-1;

LINQpad statement expecting the variable i to contain the input string. Output is stored in the o variable.

Answer 22

Haskell, 80

a%b|b<1=0-1|(\x->x==reverse x)$take(b-1)a++b`drop`a=b|1<2=a%(b-1)
f a=a%length a

Called like this:

λ> f "racercar"
5

Answer 23

Python 3, 71 bytes

def f(s,i=1):n=s[:i-1]+s[i:];return(n==n[::-1])*i-(i>len(s))or f(s,i+1)

Try it online!

Returns the 1-indexed character if the operation can be done and -1 otherwise.

Answer 24

Wolfram Language (Mathematica), 56 bytes

FirstCase[Range@Tr[1^#],a_/;PalindromeQ@Delete[#,a],-1]&

Try it online!

Takes input as a list of characters. For string input, append @*Characters.

PalindromeQ was introduced in 2015. The alternative costs +4 bytes.

Answer 25

C (gcc), 180 168 159 157 140 139 bytes

f(char*s){int j=strlen(s),m=j--/2,p=-1,i=0;for(;p&&i<m;)p=s[i++]^s[j--]&&!++p?s[i]-s[j+1]?s[i-1]-s[j]?p:j--+2:i++:p;return p<0?m+1:p?p:-1;}

Try it online!

2 16 17 bytes shaved off thanks to ceilingcat! And 3 more bytes since the rules state the minimum length of the input is 2 characters, so don't have to check for empty strings.

Ungolfed:

f(char *s) {
  int j = strlen(s);             // j = length of input
  int m = j-- / 2;               // m = midpoint of string,
                                 // j = index of right character
  int p = -1;                    // p = position of extra character
                                 //     -1 means no extra character found yet
                                 //     0 means invalid input
  int i = 0;                     // i = index of left character

  for (; p && i < m; i++) {      // loop over the string from both sides,
                                 // as long as the input is valid.
    p = s[i] ^ s[j--]            // if (left character != right character
        && !++p ?                //     and we didn't remove a character yet*)
          s[i + 1] - s[j + 1] ?  //   if (left+1 char != right char)
            s[i] - s[j] ?        //     if (left char != right-1 char)
              p                  //       do nothing,
            :                    //     else
              j-- + 2            //       remove right char.
          :                      //   else
            ++i                  //       remove left char.
        :                        // else
          p;                     //     do nothing, or:
                                 //     *the input is marked invalid 
  } 

  return p < 0 ?                 // if (input valid and we didn't remove a character yet)
           m + 1                 //   return the midpoint character,
         :                       // else
           p ?                   //   if (we did remove a character)
             p                   //     return that character,
           :                     //   else
             -1;                 //     the input was invalid.
}
```

Answer 26

JavaScript (Node.js), 75 ⁹⁰ bytes

-15 bytes thanks to @Shaggy 's conversion into a recursive function, simplification of the array comparison, and replacement of a map with a reduce.

JS might not be the right tool for this job, but i was surprised no one posted a JS answer before.

For each character of the word, we test if the removal of this character gives a word that is a palindrome, and we retain the index +1 of the last character that succeeded (or -1 if there weren't any).

f=(s,r=i=-1)=>s[++i]?f(s,(a=[...s]).splice(i,1)&&a+``==a.reverse()?i+1:r):r

Try it online!

Answer 27

Vyxal G, 58 bits^v1, 7.25 bytes

ẏ⋎:R=T›uJ

Try it Online!

Hehe vyncode go brrr

Answer 28

sed -E,  266 258 254  238 bytes

(230 bytes with ugly GNU extensions and bugs)

Unfortunally, sed needs to be tought how to count; otherwise this could have been much shorter. Anyhow, I think this is quite a clever approach and highly golfed. The idea is to put a 1 in front of the first char (line 1, along with counting helper), then to double the word with an increased number at an increased position (line 3). Then comes some overhead to count past 9 and even more overhead to count past 99. Could be golfed by switching to non-decimal output.

Finally, starting from :3, all strings are eaten up from the start and from the end, until there is only 1 or no char left. I'm pretty sure this is the shortest way to check for a palindrome.

s/.*/0123456789#:-1:1&:/
:1
s/(.)(.).*:([a-z]*)(.*)\1([a-z])([^:]*:)$/&\3\5\4\2\6/
s/([a-z])(9*)#/\10\2#/
:2
s/((.)(.).*)\2#/\1\30/
t2
/[0-9].:$/!b1
s/([a-z]*)([0-9]+)[^:]/\2\1/g
:3
s/([0-9])(.)([^:]*)\2:/\1\3:/
t3
s/.*:([-0-9]*).?:.*/\1/

Try it online!

Answer 29

Julia, 72 68 bytes

!s=[filter(i->(t=s[1:i-1]s[i+1:end])==reverse(t),1:length(s));-1][1]

Attempt This Online!

• -4 bytes: by MarcMush

Answer 30

Haskell, 118C

m s|f s==[]=(-1)|True=f s!!0
f s=[i|i<-[1..length s],r s i==(reverse$r s i)]
r s i=let(a,_:b)=splitAt (i-1) s in a++b

Ungolfed:

fix s
    |indices s==[] = (-1)
    |True = indices s!!0
indices s = [i|i<-[1..length s],remove s i==(reverse$remove s i)]
remove s i = let (a,_:b) = (splitAt (i-1) s) in a++b