Find the number of substrings of a numerical string greater than a given num string Question:
http://qa.geeksforgeeks.org/9744/vinay-queried-interesting-problem-optimization


  Input
  
  The first line contains N denoting the length of Target String. This
  line is followed by the Target String. The Target String is followed
  by an integer Q denoting the number of queries asked. After this Q
  lines follow each line containing a Query String.
  
  Output
  
  For each query output the total number of distinct Cruel Pairs that
  satisfies the given conditions.
  
  Constraints
  
  1 ≤ N ≤ 5000
  1 ≤ Q ≤ 104
  Sum of Lengths of all Query Strings ≤ 106
  All strings are composed only of '0' - '9'
  
  Sample Input

5
75201
5
78945884875
22
00048
77
501

  
  Sample Output

0
8
8
6
5

  
  Explanation
  
  Query String 1 : No such Pair exist.
  
  Query String 2 : Pairs are (1,2) , (1,3) , (1,4) , (1,5) , (2,3) ,
  (2,4) , (2,5) , (3,5)
  
  Query String 5 : Pairs are (1,3) , (1,4) , (1,5) , (2,4) , (2,5)
  
  Time Limit:1.0 sec(s) for each input file. 5s for python
  
  Memory Limit:256 MB
  
  Source Limit:1024 KB


Please review the code and help me with optimization

N = int(raw_input())

target = str(int(raw_input()))

N = len(target)

Q_N = int(raw_input())

queries_list = []
output = []


for x in xrange(Q_N):
    queries_list.append(raw_input())

for x in queries_list:
    d = int(str(int(x))[0])
    x = str(int(x))
    q_l = len(x)
    if q_l &gt; N:
        print 0
        continue
    count = 0
    for i, t in enumerate(target):
        t = int(t)
        temp = 0
        if t &gt; d:
            temp = (N - i) - q_l + 1
        elif t &gt; 0 and t &lt; d:
            temp = (N - i) - q_l
        elif t == d:
            temp = (N - i) - q_l
            if int(target[i:i + q_l]) &gt; int(x):
                temp = temp + 1
        if temp &gt; 0:
            count = count + temp

    print count
Since I misunderstood the question. I offer up a second take. I have not convinced myself that log10 will increase the efficacy of the script but I use it anyway to show the concept of using math instead of len on strings. 



The code has two generators, one to truncate the number from the left, or moving the X coordinate of the cruel pair. Another generator to move the Y coordinate.

The generator that moves the Y coordinate starts at the same length as the query string is. If the query string is longer it yields 0.  



The main function relies on the fact that if the condition are meet, all following conditions in the current substring are meet and we and we can simply add those. This means that the only check done is the check where the is of equal length + 1.  



from math import log10


def iterate_number_ints(num):
    length = int(log10(num))+1
    for i in range(length-1):
        yield num%(10**(length))
        if num // 10 ** (length - 2) % 10 == 0:
            yield 0
        length -= 1


def iterate_sub_number(num, lower_limit):
    if num &gt; 0:
        length = int(log10(num))
        lower_limit_length = int(log10(lower_limit+1))
        for n in range(lower_limit_length, length+1):
            yield num//(10**(length-n))
    yield 0


def main():

    queries = [int(x) for x in ["78945884875", "22", "00048", "77", "501"]]
    target = 75201

    for k in range(len(queries)):
        ans = 0
        for t in iterate_number_ints(target):
            if t == 0:
                continue
            length_t = int(log10(t))
            for l in iterate_sub_number(t, queries[k]):
                if l == 0:
                    continue
                length_l = int(log10(l))
                if l &gt; queries[k]:
                    ans += length_t-length_l+1
                    break

        print(queries[k], ans)


if __name__ == '__main__':
    main()




It might not be a complete solution, i can't test it, but it reduces the numbers of cases that are checked. But i should give some pointers.