Hello dear python-codeforcers!

Introduction

Python is a popular language among Codeforces enthusiasts due to its simplicity and ease of use. However, one common pitfall many Python Codeforces participants fall into is the inefficient use of string concatenation using str += str that leads to get Time Limit. In this blog post, we'll explore why this can be problematic and introduce a more efficient alternative using lists.

The Issue with str += str

When building strings iteratively, it's a common instinct to use the += operator to concatenate strings. However, what many Python developers may not realize is that this operation has a time complexity of approximately O(n^2).

Consider the following code snippet (solution for 1927B - Following the String): this solution is correct, however you are going to get Time Limit due to str += str

def solve():
    n = int(input())
    nums = list(map(int, input().split()))

    letters = [0] * 26
    answer = ''
    for i in range(n):
        for j in range(26):
            if letters[j] == nums[i]:
                letters[j] += 1
                answer += chr(97 + j)
                break

    print(answer)


def main():
    for _ in range(int(input())):
        solve()


if __name__ == '__main__':
   main()

This seemingly innocent loop has a hidden cost. In each iteration, a new string object is created, and the existing string is copied over, resulting in quadratic time complexity.

A Smarter Approach: Using Lists and str.join()

To overcome the inefficiency of str += str, we can use a list to store individual string fragments and then join them together using the str.join() method. This approach has a linear time complexity, making it more suitable for concatenating large strings.

Here's how you can refactor the previous example: same logic, but instead of str += str we used list.append() and str.join()

def solve():
    n = int(input())
    nums = list(map(int, input().split()))

    letters = [0] * 26
    answer = list()
    for i in range(n):
        for j in range(26):
            if letters[j] == nums[i]:
                letters[j] += 1
                answer.append(chr(97 + j))
                break
    answer = ''.join(answer)
    print(answer)


def main():
    for _ in range(int(input())):
        solve()


if __name__ == '__main__':
   main()

By using a list to store intermediate string fragments, we eliminate the need for repeated string concatenation, resulting in a more efficient and faster solution.

Benchmarking the Difference

Let's put the two approaches to the test with a simple benchmark (you can copy this code and test on ypu machine):

from time import perf_counter


def performance_counter(function):
    def wrapper(*args, **kwargs):
        start_time = perf_counter()
        result = function(*args, **kwargs)
        end_time = perf_counter()
        print(f'{function.__name__} took {end_time - start_time} seconds')
        return result
    return wrapper


@performance_counter
def with_str(n):
    result = ''

    for i in range(n):
        result += str(i)
    return result


@performance_counter
def with_list(n):
    result = list()

    for i in range(n):
        result.append(str(i))

    result = ''.join(result)
    return result


def main():
    result_1 = with_str(1_000_000)
    result_2 = with_list(1_000_000)


if __name__ == '__main__':
    main()

output:

with_str took 1.8441898999735713 seconds
with_list took 0.23005530005320907 seconds

You'll likely observe a significant difference in execution times, especially as the size of the concatenated strings increases.

Conclusion

Optimizing your Python Codeforces solutions is essential for achieving better performance. By avoiding the inefficient str += str concatenation and adopting the list-based approach with str.join(), you can significantly improve the speed of your code. Next time you find yourself building strings in a loop, remember to consider the impact of string concatenation and make the switch to a more efficient solution.

Happy coding on Codeforces!