trying to reduce runtime in python leetcode question-CodePudding

Edit: Because i wansn't clear i'm just gonna copy the question (my answer is the code).

Given a string obtain the alphabetically smallest string possible by swapping either adjacent 'a' and 'b' characters or adjacent 'b' and 'c' character any number of times .

Example: s = "abaacbac" The alphabetically smallest possible string is obtained by applying the following operations:

'c' ad index 5 is swapped with 'b' ad index 6 so "abaacbac" becomes "abaabcac".

Then 'b' at index 2 is swapped with 'a' at index 3 so 'abaabcac' becomes "aababac".

Finally 'b' at index 3 is swapped with 'a' at index 4 to obtain the final answer "aaabbcac".

Another example: input baacba output aabbca

here is my code

def smallestString(s):
    # Write your code here
    cons = 10 ** 5
    if len(s) > cons:
        return False
    s = list(s)
    counter = 0
    while counter < len(s):
        for i in range(len(s)):
            if i   1 < len(s):
                if s[i] == "b" and s[i   1] == "a":
                    s[i], s[i   1] = s[i   1], s[i]
                elif s[i] == "a" and s[i   1] == "b" and "c" in s[:i]:
                    s[i   1], s[i] = s[i], s[i   1]

                elif s[i] == "c" and s[i   1] == "b":
                    s[i], s[i   1] = s[i   1], s[i]

        counter  = 1
    return ''.join(s)

Is there anyway i optimize my code so it will work for very large input (max 10 seconds or it times out). ps any suggestion for different approach/modification will be good also

CodePudding user response：

Since I can't quite tell what it is you're going for here, I need to point out that the two loops you have while counter < len(s): and for i in range(len(s)): are exactly the same. So basically you are doing the "logic bit" inside the for loop for len(s) times. This might have been your intention all along but seems like a weird way to go on about it. Instead remove the while loop and the counter variable and see if you get the desired results with that.

Otherwise maybe modify the code so you can do it all in one loop (for i in range(len(s) ** 2) for example. Also the first if i 1 < len(s) statement is unnecessary and could be part of the for loop declaration (range(len(s) - 1))

CodePudding user response：

I'll assume a, b and c are the only characters (I'll comment on that at the end).

Essentially, the bs can move freely, but the as and cs can't move relatively to each other. So an easy linear time solution is to remove all bs and instead place them after the as at the start but before the first c (if any).

For your example: abaacbac → aaacac → aaabbcac

Two implementations:

import re

def smallestString(s):
    bs = 'b' * s.count('b')
    s = s.replace('b', '')
    return re.sub('(?=c|$)', bs, s, count=1)

def smallestString(s):
    bs = 'b' * s.count('b')
    s = s.replace('b', '')
    c = s.find('c')
    return s   bs if c < 0 else s[:c]   bs   s[c:]

For random strings of length 1000, I get times like these:

542.781 ms  yours
  0.038 ms  my regex-solution
  0.022 ms  my find-solution

Random might not even be the worst case for you, I'll have to think about that some more.

About my assumption that the string only contains a, b and c characters: Your task description makes it look like that, and likely it's guaranteed by the actual specification at LeetCode, as allowing other characters would only make it uglier, not harder or more interesting. You'd just extract streaks of a/b/c characters and solve each such streak as above.