Remove repetitive strings from a given sentence efficiently I recently gave a test on HackerRank:


  Given a string, return the most concise string that can be formed from it.
  
  For example:

string = 'watson  Represents|watson represents|Watson represents a first step into cognitive systems, a new era of computing.|first step into  Cognitive|Cognitive Systems; a new era|what does watson represent'

  
  
  The following string contains many duplicates like "Watson represents." We have to ignore extra spacing between characters or lower/upper case. "watson  Represents" and "watson represents" are the same thing.
  Semicolons and commas represent the same thing. For example, "Cognitive Systems; a new era" is present inside "Watson represents a first step into cognitive systems, a new era of computing."
  Your final string should not contain any duplicates. Ignore lowercase/uppercase or extra space if you have any.
  


My answer:

watson = 'watson  Represents|watson represents|Watson represents a first step into cognitive systems, a new era of computing.|first step into  Cognitive|Cognitive Systems; a new era|what does watson represent'

import re

watson = re.sub(r';', r',', watson)  #replace the semicolon with colon
watson = watson.strip().split('|')
removeWatson = list(watson)

for i in range(len(watson)):

    for j in range(len(watson)):

        if j == i:
            continue

        if " ".join(watson[i].strip().lower().split()) in " ".join(watson[j].strip().lower().split()):
            removeWatson[i] = ''

print "|".join(filter(None, removeWatson))


My answer is definitely inefficient and I am wondering if you can suggest an alternative way of solving this problem.

Most concise string:


  Watson represents a first step into cognitive systems, a new era of computing.|what does watson represent
Here's my shot at this puzzle.

Benchmark of original code, over 1,000,000 iterations (with print() commented out): 


  real    1m8.486s
  user    0m0.000s
  sys     0m0.000s


Benchmark of my code, over 1,000,000 iterations (with print() commented out):


  real    0m16.226s
  user    0m0.000s
  sys     0m0.015s  


Performance gain: 422.07%



It looks like you want to preserve the string order and uppercase/lowercase, so I took that into account. Otherwise this could be even faster/shorter.

The strategy here is to preprocess the strings, instead of going through strip(), lower(), and split() each time you need to do a comparison.
Additionally, sort the strings by length, so you only perform comparisons you need to perform. See comments for more details.

WATSON_RAW = 'watson  Represents|watson represents|Watson represents a first step into cognitive systems, a new era of computing.|first step into  Cognitive|Cognitive Systems; a new era|what does watson represent'

# 1. Preprocess the string.
#    Remove extraneous whitespace, replace semicolon with comma.
modified = ' '.join(WATSON_RAW.split())
modified = modified.replace(';', ',')


# 2. Split string by delimiter.
split = modified.split('|')


# 3. Generate string metadata, sorted by length
#    Keep track of the string contents, its index in the "split" variable, and its length.
#    Tuple has a speed advantage over list.
metadata = [(i, len(s), s.lower()) for i, s in enumerate(split)]
metadata = sorted(metadata, key=lambda x: x[1])


# 4. Uniqify the strings.
indexes_of_unique_strings = []

for index, _, string_lowercase1 in metadata:
    # Only search from current index on, skipping comparisions with earlier indexes.
    for _, _, string_lowercase2 in metadata[i:]:
        if string_lowercase1 in string_lowercase2 and string_lowercase1 != string_lowercase2:
            # This string is redundant.
            break
    else:
        # This string is unique.
        indexes_of_unique_strings.append(index)


# 5. Map indexes back to original, correctly capitalized strings, in original order.
indexes_of_unique_strings = sorted(indexes_of_unique_strings)
final = '|'.join(split[i] for i in indexes_of_unique_strings)

print(final)