Word Rank [Code Coach]

Question

For those who have solved this problem, what was your approach to the problem?
I’m not looking for the solution in code but rather just the thought process behind approaching and solving the problem.

This so far has been the only challenge I haven’t been able to finish in Python.
I’ve tried a few different approaches but they either didn’t work because I wasn’t successful in it or it was a flawed solution that only worked with single cases.

First I tried to just letter swap until I generated every possible word then index it. This became a ridiculous feet when you got to large words like SOLOLEARN.

Second I tried to index each letter to make it similar to binary treating something like "ABAB" as 0101 and comparing it to it’s alphabetical counterpart "AABB" as 0011. This in theory worked for two letters since subtracting them would give me 0100 aka 2. But going more complex I couldn’t wrap my head around it.

Third I tried looking at what my expected output should be my examining HELLO, I wrote down each outcome in a notepad:
-HELLO
Sort alphabetically
1.EHLLO
2.EHLOL
3.EHOLL
4.ELHLO
5.ELHOL
6.ELLOH
7.ELLHO
8.ELOLH
9.ELLHO
10.EOLLH
11.EOLHL
12.EOHLL
13.HELLO
By looking at it I thought I could do something like:
for each character in the word:
for the number of remaining characters:
create every word from the possible remaining letters.
add that new word to an array
index the solution and return it.

On paper it looked fine but I realized that I’m just getting rid of the first character and then running into the same problem of generating every possibility of that word.
Which I haven’t been able to wrap my head around just yet.

For those who might ask for my code for reference, I scrapped each attempt after they didn’t work so I don’t have any versions saved of my old attempts. Apologizes ahead of time.

Answer 1

To find all the permutations you can use itertools permutations.

Answer 2

Pie I haven't solved the problem, but here would be my approach (Similar to yours):

1. Find all the permutations
2. Remove duplicates
3. Rank them
4. Find the rank

However, the permutations you wrote by hand are incorrect. There are more permutations than that.

Answer 3

https://code.sololearn.com/coJTDpmruJp1

Answer 4

Although it passes all the test cases (using Python), generating all permutations isn't an efficient solution.

My approach is quite similar to the one shown here:
https://brilliant.org/wiki/rank-of-a-word-in-dictionary/#rank-of-a-word-with-repetition-of-letters

Answer 5

In Python I was lazy with sorted permutations. ;-)

For my C version I googled and implemented this:

https://www.geeksforgeeks.org/lexicographic-permutations-of-string/

Answer 6

t=0
from itertools import permutations
a=input()
s=list(permutations(a))
s=[''.join(permutations) for permutations in s]
s.sort()
dub=set()
ite=[]
for i in s:
if i not in dub:
t=t+1
ite.append(i)
dub.add(i)
if i==a:
print(t)

Answer 7

I promarily work with c++ and can anyone tell me how in the world am I suposed to accomplish something so complex with c++.
I know that I can arrange word in the alphabetic sequence and see if a word repeated itself using nested for loops but then what nothing else makes sense what should be my next step and what new should i learn coz sololearn course of c++ is very basic and does not contain useful tutorials for c++ atleast.

I know python has permutation builtin as usual with most things but I was looking for a c++ solution.

Answer 8

Hello Gaurav Kaushik ...I am still learning C. But I have already solved this problem with my own in Java without any extra implementation.
first..given String was splitted into char and sorted(a,b,c..). That was stored into a String.And act like as a probability tree.
***Target***
-No. of given String in probability tree
-skip same words(if same char on branch,results are same.Just skip)
-to stop calculating when we found the answer(to avoid the device from stunning)
😄😄 I can show my solution on paper.My algorithm. Probability tree's branch.But now I don't know how to tell you.
Just solve like as a probability tree.I think you will be solved.😊😊😊
https://code.sololearn.com/cv1TCz67zWCw/?ref=app

Answer 9

David Ashton I appreciate the code example however the second sentence of the post was about how I was *not* looking for a solution in code but rather a proper explanation.
I appreciate it none the less.