Lexicographic rank of a string(without duplicate character)

লেক্সিকোগ্রাফিক বলতে বুঝায় অ্যালফাবেটিকাল অর্ডার। যেমনঃ কোন স্ট্রিং "xyz" হলে, আমরা বলতে পারি এই স্ট্রিং এর লেক্সিকোগ্রাফিক অর্ডারের প্রথমে আছে "xyz", এরপরে "xzy" .. অর্থাৎ স্ট্রিং এর সকল পারমুটেশন এর সিরিয়াল, যারা কিনা ছোট থেকে বড় আকারে সর্টেড অবস্থায় আছে। এখন এরকম একটি স্ট্রিং দেখে আমাদের বলতে হবে এর র‍্যাঙ্ক কত। যেমনঃ "abc" এর ক্ষেত্রে, rank of "abc" = 1, rank of "acb" = 2 .... এভাবে।
একদম ব্যাসিকভাবে চিন্তা করলে আমরা সকল পারমুটেশন জেনারেট করে দেখতে পারি যে স্ট্রিং টি কততম পারমুটেশন এর সাথে মিলে গেছে। তাহলে সেটিই আমাদের স্ট্রিং এর র‍্যাঙ্ক।



এভাবে আমাদের টাইম কমপ্লেক্সিটি অনেক বেড়ে যাবে, প্রায় এক্সপোনেন্ট হারে!! (exponent) এজন্য আমাদের আরো ভালো এপ্রোচ দরকার।
আমরা একটি স্ট্রিং ধরি, "FRIEND" এর র‍্যাঙ্ক বের করতে হবে। এখানে প্রথম ক্যারেক্টার  "F" এবং "F" এর চেয়ে ছোট ২ টি ক্যারেক্টার আছে ("D", "E") এবং "F" কে তার জায়গায় ফিক্সড করলে আমাদের বাকি থাকে আরো ৫ টি জায়গা এবং "F" এর আগের ২ টি ক্যারেক্টার ঐ ৫ টি জায়গায় বসতে পারবে ৫ ফ্যাক্টরিয়াল (5!) উপায়ে। তাহলে ২ টির জন্য কম্বিনেশন হবে ২*৫!
এখন আমরা তাহলে "F" এর কাজ শেষ হলে, "F" কে ফিক্সড করে দেই। মানে "F" নিয়ে আমাদের আর মাথা ব্যথা করতে হবে না। এখন দ্বিতীয় ক্যারেক্টার "R" নিয়ে দেখি। "R" এর চেয়ে ছোট ৪ টি ক্যারেক্টার আছে ("D", "E", "I", "N"). ["F" কে আমরা ফিক্সড করে দিয়েছি, কাজেই "F" বাদ] 
তাহলে আমরা "R" এর জন্য পাবোঃ ২*৫! + ৪*৪! (আগের "F" এরগুলোও ধরতে হবে)।
একই ভাবে আমরা বাকি ক্যারেক্টার গুলোর জন্য করে ফেলিঃ

"I" = 2*5! + 4*4! + 2*3!
"E" = 2*5! + 4*4! + 2*3! + 1*2!
"N" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1!
"D" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0!
তাহলে, "FRIEND" এর জন্য র‍্যাঙ্ক হবে ঃ 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0! = 351
যেহেতু, র‍্যাঙ্ক ১ থেকে শুরু হয়, কাজেই আমাদের ফাইনাল রেজাল্ট হবে 1 + 351 = 352.



এর কপ্লেক্সিটি O(n²)। আমরা একটু বুদ্ধি খাটালে এর কমপ্লেক্সিটিকে কমিয়ে আনতে পারবো। এজন্য আমরা কিউমুলেটিভ ভাবে প্রতিটি ক্যারেক্টারের চেয়ে ছোট ক্যারেক্টারকে একটি অ্যারেতে সেভ করে রাখবো।এরপরে প্রতিবার সেখান থেকে কাউন্ট নিয়ে আমরা কাজ করবো O(n) কপ্লেক্সিটিতে