Python Bigger is Greater optimization
<p>Thank you all. I found below function which is perfect, I mark this question closed</p>

<p><a href="https://www.nayuki.io/page/next-lexicographical-permutation-algorithm" rel="nofollow">https://www.nayuki.io/page/next-lexicographical-permutation-algorithm</a></p>

<pre><code>def next_permutation(arr):

    # Find non-increasing suffix
    i = len(arr) - 1
    while i &gt; 0 and arr[i - 1] &gt;= arr[i]:
        i -= 1
    if i &lt;= 0:
        return False

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] &lt;= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return True
</code></pre>

<p>Python gurus, I am trying to finish the below challenge and don't want to use permutation.
<a href="https://www.hackerrank.com/challenges/bigger-is-greater" rel="nofollow">https://www.hackerrank.com/challenges/bigger-is-greater</a>
The below code works well for small piece of test data, however it cannot pass  100000 cases. Could any masters help to provide some suggestions to optimize the below code. Much appreciated.</p>

<pre><code>t=int(raw_input())
for _ in range(t):
    s=list(raw_input().strip())#change to list
    pos = -1#check pos, if pos is bigger, it's smallest bigger lexilogical, so only choose big pos
    i_temp=0

    for i in reversed(range(len(s))):
        for j in reversed(range(i)):
            if s[i]&gt;s[j]: #last letter is bigger than previous, in this case , we can swap to previous one, and found bigger one.
                if j&gt;pos:
                    pos=j#new place
                    i_temp=i
                    break
                if j&lt;pos:
                    break #already found good one
            if i&lt;pos:
                break #already found good one
    if  pos&gt;=0:                                              
        s_tmp=s[pos]                                          
        s[pos]=s[i_temp]                                      
        s[i_temp]=s_tmp                                          
        s1 = s[pos+1:]                  #get string for smallest   
        s1.sort()                                                
        print ("".join(s[:pos+1]+s1))            
    else:                                                        
        print ("no answer")   
</code></pre>

<p>Your instinct is right, so I'll try to help.</p>

<p>Step1: You're iterating in reverse looking for a case where a[i] &lt; a[i+n], then you know you have a solution. 
Step2: Then you paste everything (the prefix, the character, and the sorted suffix junk.) </p>

<p>Just make it easy on yourself: find the solution point first, then compute the output. Don't try to track the variables needed for step 2 in step 1. Step 2 is only going to get called once per string:</p>

<pre><code>def f(w):
    best = ''
    for i in range(len(w)):
        idx = -i-1
        c = w[idx]
        if c &gt;= best:
            best = c
        else:
            l = sorted(w[idx:])
            for j, ch in enumerate(l):
                if ch &gt; c:
                    return w[:idx] + ch + ''.join(l[:j] + l[j+1:])
    return 'no answer'

n = input()
for i in range(n):
    print f(raw_input())
</code></pre>

python algorithm