Finding the longest substring of repeating charact

Question

(this is the basis for this codeforces problem)

I try not to get help with codeforces problems unless i'm really, really, stuck, which happens to be now.

Your first mission is to find the password of the Martian database. To achieve this, your best secret agents have already discovered the following facts: The password is a substring of a given string composed of a sequence of non-decreasing digits The password is as long as possible The password is always a palindrome A palindrome is a string that reads the same backwards. racecar, bob, and noon are famous examples. Given those facts, can you find all possible passwords of the database? Input The first line contains n, the length of the input string (1 ≤ n ≤ 105). The next line contains a string of length n. Every character of this string is a digit. The digits in the string are in non-decreasing order. Output On the first line, print the number of possible passwords, k. On the next k lines, print the possible passwords in alphabetical order.

My observations are:

1. A palindrome in a non-decreasing string is simply a string of repeating characters (eg. "4444" or "11" )

2. on character i, the last instance of i - the first instance of i +1 = length of the repeating character

3. Keeping track of the max password length and then filtering out every item that is shorter than the max password length guarantees that the passwords outputted are of max length

my solution based on these observations is:

n,s = [input() for i in range(2)]#input

maxlength = 0

results = []


for i in s:
    length = (s.rfind(i)-s.find(i))+1 

    if int(i*(length)) not in results and length>=maxlength:

        results.append(int(i*(length))) 

        maxlength = length 



#filer everything lower than the max password length out
results = [i for i in results if len(str(i))>=maxlength]


#output
print(len(results))

for y in results:
    print(y)

unfortunately, this solution is wrong, in fact and fails on the 4th test case. I do not understand what is wrong with the code, and so i cannot fix it. Can someone help with this?

Thanks for reading!

Answer 1

Your program will fail on:

4
0011

It will return just 11.

The problem is that the length of str(int('00')) is equal to 1.

You could fix it by removing the int and str calls from your program (i.e. saving the answers as strings instead of ints).

Answer 2

Peter de Rivaz seems to have identified the problem with your code, however, if you are interested in a different way to solve this problem consider using a regular expression.

import sys
import re

next(sys.stdin)             # length not needed in Python    
s = next(sys.stdin)

repeats = r'(.)\1+'
for match in re.finditer(repeats, s):
    print(match.group())

The pattern (.)\1+ will find all substrings of repeated digits. Output for input

10
3445556788

would be:

44
555
88

If re.finditer() finds that there are no repeating digits then either the string is empty, or it consists of a sequence of increasing non-repeating digits. The first case is excluded since n must be greater than 0. For the second case the input is already sorted alphabetically, so just output the length and each digit.

Putting it together gives this code:

import sys
import re

next(sys.stdin)                 # length not needed in Python
s = next(sys.stdin).strip()

repeats = r'(.)\1+'
passwords = sorted((m.group() for m in re.finditer(repeats, s)),
                    key=len, reverse=True)

passwords = [s for s in passwords if len(s) == len(passwords[0])]

if len(passwords) == 0:
    passwords = list(s)

print(len(passwords))
print(*passwords, sep='\n')

Note that the matching substrings are extracted from the match object and then sorted by length descending. The code relies on the fact that digits in the input must not decrease so a second alphabetic sort of the candidate passwords is not required.