merge list of strings into one sorted string

Question

So I was tasked the following:

Given a list of strings, output a sorted string that consists of all lowercase characters (a-z) from each string in the list.

Example

[aba, xz] -> aabxz

I tried this:

from collections import Counter
from string import ascii_lowercase 
def merge(strings):
    counter = Counter()
    for string in strings:
        for char in string:
            counter[char] +=1

    result = []
    for c in ascii_lowercase:
        if c in counter:
            for _ in range(counter[c]):
                result.append(c)
    return "".join(result)

This works on most test cases, but times out on a couple test cases. I am extremely frustrated. How can I improve the time complexity of this solution?

Answer 1

counter = Counter()
for string in strings:
    for char in string:
        counter[char] +=1

You are flattening your strings list to count each individual characters. For starter, if you were to extract letters individually, you could feed it to the Counter constructor and avoid the += 1 operation. Second, flattening an iterable is best done using itertools.chain.from_iterable:

counter = Counter(itertools.chain.from_iterable(strings))

---

result = []
for c in ascii_lowercase:
    if c in counter:
        for _ in range(counter[c]):
            result.append(c)
return "".join(result)

Instead of the inner for loop, you can create repeated sequence of characters using c * counter[c]. This also have the neat advantage to produce the empty string ('') when counter[c] is 0, removing the need for the c in counter test:

return ''.join(c * counter[c] for c in ascii_lowercase)

---

These changes result in a ×4 speedup on my machine.

Answer 2

I have a few comments regarding the code:

• Docstrings: Python documentation strings (or docstrings) provide a convenient way of associating documentation with Python modules, functions, classes, and methods. It's specified in source code that is used, like a comment, to document a specific segment of code. You should include a docstring to your public functions indicating what they return and what the parameters are.

  def merge(strings):
  

  should be:

  def merge(strings):
      """Join and return a sorted string for lowercase letters found in strings(a list of strings) members.
  

• Counter dict

  counter = Counter()
  for string in strings:
      for char in string:
          counter[char] +=1
  

  This is the wrong form of using Counter()

  This is the correct form: (No need for counter[char] +=1 which is done automatically)

  counter = Counter(''.join([char for word in strings for char in word if char.islower() and char.isalpha()]))
  

And the code could be simplified using list comprehension which is much more efficient than explicit loops and calls to append as well as storing letters into a dictionary:

def merge2(str_list):
    """Join and return a sorted string of lower case letters found in every str_list member."""
    return ''.join(sorted([letter for word in str_list for letter in word if letter.islower() and letter.isalpha()]))

if __name__ == '__main__':
    start1 = perf_counter()
    merge(['abcD' for _ in range(10000000)])
    end1 = perf_counter()
    print(f'Time: {end1 - start1} seconds.')
    start2 = perf_counter()
    merge2(['abcD' for _ in range(10000000)])
    end2 = perf_counter()
    print(f'Time: {end2 - start2} seconds.')

Results (about half the time for a large list):

Time: 14.99056068 seconds.

Time: 7.373776529999999 seconds.

Answer 3

My general approach of an algorithm, in readable form. It is in C#, but it should be clear enough to read. And I personally prefer an algorithmic sketch over a 1-liner, for the sake of clarity. Dictionary is the same as hash table, and StringBuilder is like a list of chars (because strings are immutable in C#). I did not test timing.

    public string Count(List<string> strings)
    {
        var mapping = new Dictionary<char, int>();
        for (char c = 'a'; c < 'z'; c++)
        {
            mapping[c] = 0;
        }
        foreach (var str in strings)
        {
            foreach (var ch in str)
            {
                if(Char.IsLower(ch))
                {
                    mapping[ch]++;
                }
            }
        }
        var b = new System.Text.StringBuilder();
        for (char c = 'a'; c < 'z'; c++)
        {
            b.Append(c, mapping[c]); // Append(c, i) : adds c i times
        }
        return b.ToString();
    }