3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ When you state I tried this does it work, but with a timeout, or doesn't it work at all? \$\endgroup\$ – dfhwze Sep 16 at 10:59
  • \$\begingroup\$ it works with a timeout \$\endgroup\$ – nz_21 Sep 16 at 11:02
3
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ I see, thank you. Time complexity wise, is there any difference between the optimized solution and the one mentioned in the question? \$\endgroup\$ – nz_21 Sep 16 at 11:54
  • \$\begingroup\$ @nz_21 No, this is the exact same algorithm. \$\endgroup\$ – 409_Conflict Sep 16 at 11:54
  • \$\begingroup\$ I see. Time to stop using python then for stupid hackerrank challenges. I'm very frustrated at my results. \$\endgroup\$ – nz_21 Sep 16 at 11:55
  • \$\begingroup\$ @nz_21 A side remark: you can change to use the PyPy interpreter (using the same code) for faster running time. But it would be better to also learn how to make a Python implementation run faster. \$\endgroup\$ – GZ0 Sep 16 at 15:37
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ is this faster than the solution in the question for big inputs? My question was specifically about improving time complexity. This solution is slower as it uses sorting \$\endgroup\$ – nz_21 Sep 16 at 11:25
  • \$\begingroup\$ I edited the code and you can try this test yourself (about half the time taken by your code) \$\endgroup\$ – user203258 Sep 16 at 11:33
  • \$\begingroup\$ And apart from this code being 2x faster than yours when tested for large input, from my understanding the question indicates that the output should be SORTED STRING which is exactly what you got. \$\endgroup\$ – user203258 Sep 16 at 12:09
-1
\$\begingroup\$

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();
    }
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You've provided an alternate implementation, but you haven't reviewed the original code. Please edit your answer to explain what your answer is an improvement on and review the code in the question. \$\endgroup\$ – Dannnno Sep 16 at 14:12
  • \$\begingroup\$ According to @nz_21 his solution works "most of the time", and he/she worries about complexity. I am showing the basic algorithm, without any fancy library functions to show what I believe is the fundamental algorithm for solving this. I also cannot see a way that could possibly be faster (other than how the hash table is implemented). \$\endgroup\$ – Alexander Sep 17 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.