HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Find the longest string without repeating a letter

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
withouttherepeatingfindletterlongeststring

Problem

I've written some code to scan large files and search for long strings that you can write without repeating a letter. I'm self-taught in python and I'm wondering what I've missed.

import sys
letters ={} #letters is a dictionary
currentResult=""
ideas=[]
with open(sys.argv[1]) as f:
  while True:
    c = f.read(1)
    if not c:
      print "End of file"
      break
    if c in letters:
        letters={}
        temp=currentResult.rsplit(' ',1)[0]
        ideas.append(temp.rstrip('?:!.,;'))
        currentResult=""
    currentResult+=c
    if not c.isspace():
        letters[c]=True
ideas=sorted(set(ideas))
ideas.sort(lambda x,y: cmp(len(x), len(y)))
for x in ideas:
    print x.strip()

Solution

I do believe the algorithm in the pervious answer and in the OP does not do what the OP wanted. It test for the longest string starting with the line's first character, and then repeat from the first non repeating string. For example if the string is

abcaefgb


The algorithm given will return

abc


while the right answer should be

bcaefg


I believe the following algorithm will find the right string. Note that if there are several equal length longest strings it will return the first

def scantillrepeat(line):
    found = ''
    for char in line:
        if not char in found:
            found = found + char
        else:
            break
    return found

def findlongest(f):
    for line in f:
        longestfound = ''
        longestfoundlen = 0
        for k in range(len(line)):
            candidate = scantillrepeat(line[k:])
            if len(candidate) > longestfoundlen:
                longestfound = candidate
                longestfoundlen = len(candidate)
    return longestfound


To test

In [39]: f = ['abcaefgb']

In [40]: findlongest(f)
Out[40]: 'bcaefg'


Note that my version does not allow joining lines separated by newline \n. This should be altered if needed.

Code Snippets

def scantillrepeat(line):
    found = ''
    for char in line:
        if not char in found:
            found = found + char
        else:
            break
    return found


def findlongest(f):
    for line in f:
        longestfound = ''
        longestfoundlen = 0
        for k in range(len(line)):
            candidate = scantillrepeat(line[k:])
            if len(candidate) > longestfoundlen:
                longestfound = candidate
                longestfoundlen = len(candidate)
    return longestfound
In [39]: f = ['abcaefgb']

In [40]: findlongest(f)
Out[40]: 'bcaefg'

Context

StackExchange Code Review Q#133943, answer score: 4

Revisions (0)

No revisions yet.