Minimum Expression

আমাদের একটা string দেওয়া হল যেটাকে আমরা চাইলে rotate করতে পারি । মানে একদম লাস্ট এ যে ক্যারেক্টারটা আসে তা আমরা একদম প্রথমে নিয়ে যেতে পারি । এবং বাকি ক্যারেক্টারগুলা এক ঘর করে রাইট সাইটে সরে যাবে । আমাদের বলতে বলা হল আমরা মিনিমাম কতটা এমন rotate করে string এর lexicographically smallest string  করতে পারি ।

আমাদের যদি n size এর এমন কোন array দেওয়া থাকে যার মধ্য দেখে আমাদের বলতে বলা হয় সবথেকে মিনিমাম নাম্বার/ ভ্যালু এর ইনডেক্সটা কি তাহলে আমরা কি ভাবে কাজ করি - 

এখন যদি আমরা একই কাজটা string rotation এর জন্য করতে চাই তাহলে কিভাবে করব -
এইখানে আমরা দেখি আমাদের রান টাইম হচ্ছে O(n^2) কারণ এই rotation( i ) > rotation ( j ) operation টা করার জন্য আমাদের O(n) টাইম যাচ্ছে এবং কাজটা আমাদের করতে হচ্ছে n বার মানে আমাদের টোটাল O(n^2) লেগে যাচ্ছে কাজটা করতে । string এর সাইজ যদি অনেক বড় হয় তাই আমাদের টাইম লিমিট এর মধ্যে এইভাবে করে আমরা পারব না , TLE খেয়ে যাব ।  আমরা যদি কিছু মোডিফিকেশন করতে পারি তাহলে আমরা কোডটাকে O(n) এ নিয়ে আসতে পারি ।

এই lexicographical string rotation O(n) এর এলগরিদমটা প্রথম দেন "Zhou Yuan" . আমরা rotation( i ) > rotation( j ) এই অপারেশনটার কয়েকটা Observation খেয়াল করি ।

Observation 1 :

যদি ইনডেক্স 'i' এর string থেকে ইনডেক্স 'j' এর string ( মানে rotation করার পর ( i , j ) থেকে যে stringটা স্টার্ট হয়ে আমরা যে string পাই সেই string ) ছোট হয় তাহলে আমরা বলতে পারি  s[ i + p ] = s [ j + p ] and s [ i + k ] < s [ j + k ] যেখানে ০ <= p < k আর i + k < length_of_the_string .

মানে i index স্ট্রিং j index এর string থেকে p টা ভ্যালু সমান হলেও j থেকে  k নাম্বার value টা i থেকে k নাম্বার ভ্যালুটার থেকে বড় ।

Observation 2 :
যেহেতু rotation ( i ) < rotation ( j ) যেখানে j + k নাম্বার পজিশন এ আমাদের i  + k থেকে বড় ভ্যালু পাওয়া যাচ্ছে , তাই আমাদের নেক্সড ক্যালকুলেশন এর জন্য j + k ভ্যালু বাদ দিতে পারি কারণ সবার জন্যই আমরা k নাম্বার পজিশন এ এসে বড় ভ্যালু পেয়ে যাব  তাই  আমরা নেক্সড comparison start করব i index এর সাথে  j + k + 1 index এর  ।

কোড

এই কোডের রান টাইম হবে O(n) .

Practice Problem ::: 1 , 2 , 3 , 4