0

I have a string, say txt='string'. The goal is to count for every character, find the number of smaller characters on right . Hence the output should be;

Final Output

{s:4,t:4,r:3,i:1,n:1,g:0}. For example, s has 4 smaller characters on right; r,i,n,g.

I used following code to get number of characters smaller than particular character;

arr=[0]*255
txt='string'
for i in range(len(txt)):
    arr[ord(txt[i])]+=1
lst=[idx for idx, element in enumerate(arr) if element==1]
d={}
for j in range(1,255):
     arr[j]+=arr[j-1]
for k in lst:
      d[chr(k)]=arr[k]-1

This gives following output; {'g': 0, 'i': 1, 'n': 2, 'r': 3, 's': 4, 't': 5}. for example n has 2 characters smaller than it in this string; g,i. But the question is, how do we know how many of those characters are on the right of n. Help is appreciated.

Selcuk
  • 57,004
  • 12
  • 102
  • 110
jay
  • 1,319
  • 6
  • 23
  • 42

1 Answers1

2

You are overcomplicating things. Try this method:

text = "string"
d = dict.fromkeys(text, 0)
for i, s in enumerate(text):
  for p in text[i:]:
    if p < s:
      d[s] += 1

the value of d would be:

{'s': 4, 't': 4, 'r': 3, 'i': 1, 'n': 1, 'g': 0}

See this question to understand how text[i:] returns the characters after the current one if you don't know the slice notation.

Selcuk
  • 57,004
  • 12
  • 102
  • 110
  • appreciate your help and showing me a new approach. Will it be possible to do it in linear time, rather than quadratic time as you have shown above. kindly advise. – jay Dec 24 '21 at 18:06