# 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.

• No examples posted? And what to output if it is not possible to make the input into a Palindrome? Apr 3, 2014 at 18:55
• @Arm103 you are still missing the examples you are referring to Apr 3, 2014 at 19:14
• Warning: "(see example 3)". This suggests that this is homework since no examples were ever posted. Apr 3, 2014 at 19:55
• @Quincunx Be sure to read the thread on the Mathematica submission, too. :-) Apr 3, 2014 at 20:01
• This question appears to be off-topic because example 3 is missing from the question. Apr 4, 2014 at 3:15

# 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

• I should learn J. Any tutorials for a python programmer? Apr 3, 2014 at 20:27
• @Synthetica the official one is good Apr 3, 2014 at 20:28
• @Synthetica Nothing specifically for Pythoners, but J for C Programmers is a great resource for anybody migrating from imperative programming. Apr 3, 2014 at 20:30

# 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?) • +1 for "Not PHP" ;) Apr 3, 2014 at 19:28 • <?php$line = fgets(STDIN); ?> Apr 3, 2014 at 19:28
• @User011001 Where would that fit in? Apr 3, 2014 at 19:55
• You could save a char each by writing 1>0 instead of True and by removing the space between ] and for in ...[::-1] for g...
– Kaya
Apr 3, 2014 at 20:53
• @Kaya You can simply use 1 instead of True as well. 1 == True, after all. Apr 4, 2014 at 13:38

## Mathematica, 1069887 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]]

• @Arm103 I could, but I'll leave that to someone else. ;) Apr 3, 2014 at 19:08
• @Arm103 wait, is this your homework? Apr 3, 2014 at 19:14
• @JanDvorak There are CS courses that use PHP? That would be scary. Apr 3, 2014 at 19:15
• @Arm103 no. You can't ;-) Apr 3, 2014 at 19:16
• @JanDvorak hmmm, what's a program in Mathematica? Apr 3, 2014 at 19:29

### 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

• Guess there must be a shorter way but I didn't find it. Apr 3, 2014 at 21:14
• RACECAR is still a palindrome with the E. Is it necessary to specify a character to remove, when the inputted word is already a palindrome? Apr 3, 2014 at 22:12
• @unclemeat, yes. Penultimate sentence of the spec. Apr 3, 2014 at 22:17
• Why -2]$-1=)? At the start of that block you have at most one item on the stack, so you can easily shorten to -2]0=). (Or for the same length, ]-2or). I've learnt to love or for special cases). Apr 3, 2014 at 22:21 • @Howard If I had a nickel for every time I felt that way about Golfscript... Apr 3, 2014 at 23:21 # 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?  # 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. • This outputs the last index instead of -1 if no palindrome is found (i.e. aaabb outputs 5 instead of -1). Aug 21, 2019 at 7:54 • @KevinCruijssen: Right you are. I fixed it at the cost of 2 bytes. Aug 21, 2019 at 15:08 # 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- # 05AB1E, 10 9 bytes ā.Δõs<ǝÂQ  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)  # 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]. • If you used the Rebmu dialect that first solution is just 37 characters, despite being basically the same code :-) Invoke as rebmu/args "Rng01rpNl?A[ThdRMatCYaNieTrvCYt[Rn]]r" "racecar". Note that the Rebmu documentation has been improved, and recent changes have tightened it up a bit...still looking to feedback before everyone and their D starts using it. :-) Apr 6, 2014 at 22:05 # 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); }  • Yay fun!!!!! :) – Almo Apr 4, 2014 at 15:23 • In the golfed version, where is R defined and used? Apr 5, 2014 at 10:31 • oh yeah, it should say var R = s.Remove(i,1). good catch Apr 5, 2014 at 14:56 # Not Python PHP, 8583 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,$d+1):-1;}


Try it online!

# Brachylog, 20 bytes

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


Try it online!

It was too long

• Oct 6 at 6:39

# 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!

• You can save some space by not wrapping in a function/method. However your code currently returns 0-based index (needs to be 1-based) and it also needs to return -1 if no palindrome found. Apr 4, 2014 at 16:06
• Fixed the -1, thanks. Not sure what you have in mind regards taking it out a method though, I'll have a think. Apr 4, 2014 at 17:31
• Ok, took your advise on board and rewrote it :), ty. Apr 4, 2014 at 17:40
• You're welcome! Now that is much better :) +1 Apr 4, 2014 at 18:45

# 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.

# Perl 5-p, 56 52 bytes

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


Try it online!

• i came across this answer, 44bytes : Try it online! Oct 13 at 11:20

# 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))

• Welcome to CGCC! This site is for competitive coding challenges, and this challenge is tagged code-golf, so answers are expected to be as short as possible. You can improve your answer's score by doing things like eliminating unnecessary whitespace, shortening variable names, and using tips that can be found here. Nov 11, 2022 at 17:35
• How many bytes is this? Nov 11, 2022 at 18:07
• I have submitted an edit to add the link to the Python website, and also count the byte counts for this one (not including the extra two lines, which are for running solutions). Feel free to edit this if you want to make some changes on your own.
– oeuf
Nov 12, 2022 at 4:46

# C++, 247 150 bytes

-97 thanks to ceilingcat

#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';


# 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


(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


## 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.Length){var x=a.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.Length)
{
// create a string with the i-th character removed
var x = a.Remove(i++, 1);
// and test if it is a palindrome
if (x == new string(x.Reverse().ToArray())) r = i;
}
Console.Write(r);
}
}


# 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.

a%b|b<1=0-1|(\x->x==reverse x)$take(b-1)a++bdropa=b|1<2=a%(b-1) f a=a%length a  Called like this: λ> f "racercar" 5  # 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. # 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. # C (gcc), 180168159157140 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. } $$$$  • @ceilingcat That &&!++p is just devious to explain :) Aug 22, 2019 at 17:51 # JavaScript (Node.js), 75 90 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! • 77 bytes Jul 7 at 13:20 • 75 bytes Jul 7 at 13:35 • @Shaggy Thanks! I'm still not entirely confortable with recursive functions, but i should have seen that for once the reduce was shorter. Nice trick for the array comparison, i didn't know about it! Jul 7 at 14:16 # VyxalG, 58 bitsv1, 7.25 bytes ẏ⋎:R=T›uJ  Try it Online! Hehe vyncode go brrr # 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! # Julia, 72 68 bytes !s=[filter(i->(t=s[1:i-1]s[i+1:end])==reverse(t),1:length(s));-1]  Attempt This Online! • Oct 12 at 11:13 ## 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
`