Minimum Expression

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

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

	void solve()
	{
	int i = 0 , j ;
	for ( j = 1 ; j < n ; j++ )
	if( array[i] > array[j] ) i = j ;
	return i ;
	}

view raw ME1.cpp hosted with ❤ by GitHub

এখন যদি আমরা একই কাজটা string rotation এর জন্য করতে চাই তাহলে কিভাবে করব -

	void solve()
	{
	int i = 0 , j ;
	for ( j = 1 ; j < n ; j++ )
	{
	if( rotation( i ) > rotation( j ) ) i = j ;
	}
	return i ;
	}

view raw ME2.cpp hosted with ❤ by GitHub

এইখানে আমরা দেখি আমাদের রান টাইম হচ্ছে 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 এর  ।

কোড

	int minimumExpression ( string s )
	{
	s = s + s ;
	int len = s.size() , i = 0 , j = 1 , k = 0 ;
	while( i + k < len && j + k < len )
	{
	if( s[i + k] == s[ j + k ] ) k++;
	else if( s[i + k] > s[ j + k] )
	{
	i = i + k + 1 ; // surely can escape this points
	if( i <= j ) i = j + 1 ; // as j is smallest now we will start from j + 1 minimum
	k = 0 ;
	}
	else if ( s [ i + k ] < s[ j + k ] )
	{
	j = j + k + 1 ;
	if ( j <= i ) j = i + 1 ;
	k = 0 ;
	}
	}
	return min( i , j ) ;
	}

view raw ME3.cpp hosted with ❤ by GitHub

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

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