# [SOLVED] two commands in comprehension

## Issue

Sorry if the title is inaccurate but I’m unsure how to title this as I am kind of a rookie.

I am trying to solve a challenge:

"Complete the function `scramble(str1, str2)` that returns `True` if a portion of `s1` characters can be rearranged to match `s2`, otherwise returns `False`."

So first i wanted to complete it like this:

`return True if "".join(str(e) for e in s2 if e in s1 and s1.count(e) >= s2.count(e)) == s2 else False`

However, this times out and apparently is not sufficiently optimized.

Oblivious as I am I assume it has something to do with the `count()` method so instead I am trying to remove `e` from `s1` below if `e` is in `s1` – because when a character from `s2` is found in `s1` it can not be used again (unless more of same character exist in `s1`. So for example `s2 = 'stress'` would need 3 x `'s'` occurences in `s1` for the function to return `True`.

however, in the code below it seem like this part: `s1.replace(e, '', 1)` does not do anything when I print before/after.

``````def scramble(s1, s2):
print(s1)
("".join(str(e), s1.replace(e, '', 1)) for e in s2 if e in s1)
print(s1)
scramble('abcdefghijklmnopqrstuvzxy', 'stress')
``````

What can I do?

## Solution

Your algorithm iterates over each character in `s2`, and then finds the character count of that character for `s1` and `s2`. For ease of notation, let `m = len(s1)` and `n = len(s2)`. Then, each `.count()` operation takes linear time in the number of characters in the string invoking `.count()`. So, we have `O(n)` iterations, and `O(m + n)` work per iteration — our final runtime is `O(n*m + n^2)`. If `s2` is really long, we’re going to see a lot of slowdown.

We can do better, by generating the counts before beginning to analyze them.

``````# You can use collections.Counter() here, but I've chosen to forgo this to make the runtime analysis clearer.
def count_characters(s):
chars = {}
for char in s:
if char in chars:
chars[char] += 1
else:
chars[char] = 1
return chars

def scramble2(s1, s2):
s1_characters = count_characters(s1)
s2_characters = count_characters(s2)

for char in s2_characters:
if char not in s1_characters or s1_characters[char] < s2_characters[char]:
return False

return True
``````

Let’s analyze the runtime of the revised algorithm:

`count_characters()` is linear in the length of the input string. So the character counters take `O(m + n)` time to generate. Then, we need to examine each counter in `s2_characters`, and compare it with a counter in `s1_characters`. Regardless of whether you assume the alphabet is constant size, this takes `O(n)` time in the worst case. So, the final runtime is `O(m + n)` — i.e. linear in the lengths of the input strings.