লংগেস্ট কমন সাব-সিকুয়েন্স (Longest Common Subsequence)

২ টি স্ট্রিং দেয়া থাকবে। এদের মাঝে ম্যাক্সিমাম কত দৈর্ঘ্যের সাব-সিকুয়েন্স আছে, এবং সিকুয়েন্সটি কি, এটা আমাদের বের করতে হবে।
সাব-সিকুয়েন্স হল এমন একটি সিকুয়েন্স, যা কিনা ২ টি স্ট্রিং এর মাঝে কমন ক্যারেক্টার নিয়ে তৈরী এবং, একটি ক্যারেক্টার এর ইনডেক্স এর চেয়ে পরের ক্যারেক্টার এর ইনডেক্স (একটি নির্দিষ্ট স্ট্রিং) অবশ্যই বড় হবে।
যেমনঃ
String X = "AAABCD"
String Y = "ABCDDA"
তাহলে, এদের মাঝে LCS হবেঃ "ABCD"
ধরি Z = "ABCD"
এখানে দেখা যাচ্ছে যে, A,B,C,D এর প্রত্যেকটি ক্যারেক্টার এর ইনডেক্স তার আগের ক্যারেক্টার থেকে বড় (X এবং Y উভয় স্ট্রিং এ)। আমরা মেইনলি ক্যারেক্টার এর অর্ডার মেইনটেইন করবো।

এপ্রোচঃ প্রথমে আমরা X এর i-তম prefix (ক্যারেক্টার, যা অন্য ক্যারেক্টার এর আগে বসাই) কে Xi দিয়ে প্রকাশ করি। তাহলে,
X1 = "A"
X3 = "AAA" etc..
এখন আমরা খেয়াল করি,

• যদি, Xi == Yj হয়, (অর্থাৎ ২ টি স্ট্রিং এর ক্যারেক্টার মিলে গেছে), তাহলে, Zs = Xi = Yj হবে, এবং Zs-1, Xi-1 এবং Yj-1 এর একটি LCS হবে
• যদি, Xi != Yj হয়, তাহলে Zs != Xi বলতে আমরা বুঝাবো, ্Z , Xi-1 এবং Yj এর একটি LCS
• যদি, Xi != Yj হয়, তাহলে Zs != Yj বলতে আমরা বুঝাবো, ্Z , Xi এবং Yj-1 এর একটি LCS

তাহলে, যখন ক্যারেক্টার সমান হবে না, তখন আমরা ২ স্ট্রিং এর মাঝে ক্যালকুলেট করে ম্যাক্সিমাম মানকে নিবো।তাহলে আমাদের অ্যালগরিদম অনেকটা এরকমঃ

c[ i,j ] = 0; if i == 0 OR j == 0
              c[ i-1,j-1 ] + 1; if i,j > 0 AND Xi == Yj
              max ( c[ i,j-1 ], c[ i-1,j ] ); if i,j > 0 AND Xi != Yj

LCS ক্যালকুলেশন

ধরি, X = "ABCBDAB", Y = "BDCABA"
এখন আমরা একটি 8x7 সাইজ এর ২-ডি অ্যারে নিবো। 8 = X.size()+1, 7 = Y.size()+1

আমাদের অ্যারের [0,0] ইনডেক্স 0 ইনিশিয়ালাইজ করবো। এরপরে আমরা প্রতি সারি-কলামে ২ টি স্ট্রিং থেকে ভ্যালু মিলানোর চেষ্টা করবো। এবং আমাদের অ্যালগরিদম অনুযায়ী মান বসাবো। এখন খেয়াল করে দেখবো যে, ইনডেক্স ১ এর A(String X) এর সাথে ইনডেক্স ১ এর B (String Y) মিলেনি, কাজেই আমরা [1,1] ইনডেক্স এ 0 বসিয়ে দিলাম। এই 0 এসেছে, [1,0] এবং [0,1] ইনডেক্স এর ভ্যালুর মাঝের ম্যাক্সিমাম ভ্যালু। অর্থাৎ max ([1,0] এবং [0,1]) = 0।

এর মানে হল, X1 এবং Y1 এর মাঝে LCS এর দৈর্ঘ্য = 0. এভাবে আমরা টেবিল ফিল আপ করতে থাকি।

এখানে, 1(A) এর সাথে 4(A) মিলে গেছে, তাই আমরা [0,3] ঘরের ভ্যালু + ১ বসাবো। এভাবে আমরা বাকি ভ্যালুর জন্য ঘর ফিল আপ করলে এরকম একটি ফাইনাল টেবিল পাবো।

কাজেই, আমাদের LCS স্ট্রিং এর দৈর্ঘ্য হচ্ছে 4.
কোডঃ

এখন আমাদের কাজ হবে, এই যে LCS স্ট্রিং টির দৈর্ঘ্য পেলাম, একে প্রিন্ট করা। এর জন্য আমাদের পাথ বের করতে হবে। আমরা আমাদের ফাইনাল রেজাল্ট থেকে উপরে এবং বামে মুভ করতে থাকবো, যখন আমরা দেখবো যে Xi == Yj, তখন আমরা সেই ঘরের ভ্যালু প্রিন্ট করে দিবো। আমরা যদি পাথ ফাইন্ডিং এর জন্য টেবিল জেনারেট করি, দেখতে এরকম হবে ফাইনালিঃ

এই হচ্ছে আমাদের ফাইনাল পাথ টেবিল। আমরা নিচ থেকে উপরে সিকুয়েন্স অনুযায়ী উঠতে থাকবো। আমরা LCS বের করার সময়, যখন অ্যারেতে ভ্যালু আপডেট করতাম, ঐ সময়, আমরা আমাদের পাথ টেবিল ও আপডেট করে দিবো। Xi == Yj হলে আমরা টেবিলে স্টোর করবো m, তানাহলে, আমাদের চেক করতে হবে যে c[i-1,j] কি c[i,j-1] থেকে বড় অথবা সমান কিনা। এক্সদি বড় অথবা সমান হয়, তাহলে আমরা স্টোর করবো u (up), তানাহলে, আমরা l(left) স্টোর করবো। তাহলে আমাদের LCS স্ট্রিং: "BCBA" এরপরে আমরা নিচের কোড অনুযায়ী পাথ ক্যালকুলেট করবোঃ

এখানে char x[] হল X স্ট্রিং, আমরা এখানে ইচ্ছা করলে Y ও পাঠাতে পারতাম। যেহেতু, ২ স্ট্রিং এর মাঝের কমন স্ট্রিং বের করতে চাচ্ছি, কাজেই, আমাদের ২ টি স্ট্রিং চেক না করে একটির ইনডেক্স চেক করলেই কাজ হয়ে যাচ্ছে

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Uva: 10192 - Vacation
• Uva: 10405 - Longest Common Subsequence
• Uva: 10635 - Prince and Princess
• Hacker Earth: Longest Common Subsequence
• Hackerrank: LCS Returns
• Light Oj: An Easy LCS
• Spoj: Cross country
• Codechef: Chef and LCS

স্লাইডিং উইন্ডো (Sliding Window Technique)

প্রোগ্রামিং কন্টেস্টে আমাদের অনেক সময় ৩ বা ৪ বা এরচেয়েও বেশি লুপ এর কোড লিখতে হয়। ব্যাসিকালি ব্রুটফোর্স যাকে বলে। এখন আমরা যেই টেকনিক দেখবো, এটি এরকম একাধিক লুপ এর প্রব্লেমকে কম সময়ে সল্ভ করে দিতে পারবে।

স্লাইডিং উইন্ডো সমস্যার বিভিন্ন রূপ আছে। কিন্তু তাদের সবারই একটি কমন বৈশিষ্ট আছে : একটি সাব-অ্যারেকে (আমরা একে 'উইন্ডো' বলে থাকি, যা স্ট্যাটিক বা ডাইনামিক দৈর্ঘ্য থাকতে পারে) আমরা  n সংখ্যক উপাদানগুলির অ্যারে এর বাম থেকে ডান দিকে লিনিয়ারভাবে সরায়ে কিছু কম্পিউট করার চেষ্টা করবো। এভাবে উইন্ডো স্লাইড করার টেকনিক কেই স্লাইডিং উইন্ডো বলে। স্লাইডিং উইন্ডোর অনেক রকম ভ্যারিয়েশন আছে। যেমন ঃ 

1. একটি অ্যারের মাঝে ফিক্সড সাইজের কোন সাব-অ্যারের ম্যাক্সিমাম সামেশন বের করা। যেমন ঃ অ্যারে  A = {10, 40, 10, 30, 20} এবং উইন্ডো সাইজ w = 3 হলে, মাক্সিমাম সামেশন = 40+10+30 = 80.
   
2. একটি অ্যারের মাঝে ফিক্সড সাইজের সকল সাব-অ্যারের ম্যাক্সিমাম অথবা মিনিমাম সংখ্যা বের করা। যেমন ঃ
   অ্যারে A = {0, 5, 5, 3, 10, 0, 4} , n = 7 এবং উইন্ডো সাইজ w = 3, হলে এখানে n-w+1 = 5 টি ভিন্ন ভিন্ন সাব-অ্যারে আছে যাদের সাইজ = 3; {0, 5, 5}, {5, 5, 3}, {5, 3, 10}, {3, 10, 0}, {10, 0, 4}. এবং আমরা এদের ম্যাক্সিমাম সংখ্যা বের করতে চাইলে এগুলি হবে ঃ 5, 5, 10, 10, 10 প্রতি সাব-অ্যারের জন্যে।
   
3. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর, যার এলেমেন্ট এর সাম, নির্দিষ্ট কোন সাম S থেকে বড়/ সমান/ ছোট হয়। যেমন ঃ অ্যারে A = {5, 1, 2, 3, 4, 2} এবং S = 7 হলে,
   মিনিমাম দৈর্ঘ্য == 7 : 2,  {5, 1, 2, 3, 4, 2}
   মিনিমাম দৈর্ঘ্য > 7 : 3,  {5, 1, 2, 3, 4, 2} , {5, 1, 2, 3, 4, 2}, {5, 1, 2, 3, 4, 2}
   মিনিমাম দৈর্ঘ্য < 7 : 1,  {5, 1, 2, 3, 4, 2} ; যেকোনটাই হতে পারে।
   
4. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর যাতে  [ 1 to w ] পর্যন্ত সকল সংখ্যা কমপক্ষে একবার করে হলেও থাকবে। যেমনঃ A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} এবং w = 4, আমরা 13 length এর একটি সাব-অ্যারে পাবো, যাতে 1, 2, 3, 4 আছে। এই সেইম অ্যারের জন্যে যদি w = 3 হয়, তাহলে A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} আমরা 3 length এর একটি সাব-অ্যারে পাবো। 

সলুশন (Solution)
উপরের প্রবেল্মগুলি আমরা নরমালি বারে বারে লুপ চালায়ে সল্ভ করতে পারবো তখনি, যখন রেঞ্জ কম হবে, যা আমাদের given time এর মাঝে সল্ভ করা সম্ভব হয়। আমরা ব্রুটফোর্স এর ব্যাপারগুলি বাদ দিয়ে সরাসরি আমাদের স্লাইডিং উইন্ডো টেকনিক এ চলে আসি, যা কিনা O (n) সময়ে সল্ভ করতে সক্ষম।

১ম টেকনিক (First Technique):

আমরা প্রথমে উইন্ডো তে আমাদের প্রথম w টি ইন্টিজার ইন্সার্ট করে দিলাম এবং এদের সাম বের করে তাকে curr_sum ভ্যারিয়েবল এ রাখলাম। এরপরে আমরা স্লাইড করে করে আগাবো। আমরা ডান পাশে একটি একটি করে এলেমেন্ট উইন্ডো তে ইন্সার্ট করবো এবং বাম দিক থেকে একটি করে সরায়ে দিব, ফলে আমাদের উইন্ডোর সাইজ সেইম থাকবে।এলেমেন্ট ইন্সার্ট এর সময় আমরা চেক রাখবো যে এখন আমরা ম্যাক্সিমাম সাম পেলাম কিনা। প্রতিবার ইন্সার্ট করার সময় আমাদের নতুন সাম হবে curr_sum + inserted_element - removed_element. এভাবে আমরা পুরো অ্যারেকে স্লাইড করে রেসাল্ট পাবো।

২য় টেকনিক (Second Technique):

যদি n এর মান অনেক বড় হয়, সকল সাব-অ্যারের মাক্স/মিন বের করা একটু কঠিন হবে। এজন্য আমরা deque (double ended queue) ব্যবহার করবো। এখন আমাদের উইন্ডো হবে আমাদের deque টি। আমরা deque কে ascending order ( ছোট থেকে বড় ) এ সাজাবো ( যদি মিন বের করতে চাই)। deque এর প্রথম দিকে আমাদের মিনিমাম এলেমেন্ট গুলি থাকবে। কিন্তু এভাবে কাজ করতে গেলে একটি বড় প্রব্লেম হল, আমাদের মূল অ্যারের ইন্ডেক্সগুলি উল্টাপাল্টা হয়ে যাবে, এজন্য আমাদের ইন্ডেক্স এর ট্র্যাক রাখতে হবে যাতে আমরা বুঝতে পারি যে, এলেমেন্ট উইন্ডো তে আছে কি নাই। নিচের একটি স্যাম্পল কোড দেয়া হল ঃ

৩য় টেকনিক (Third Technique):

আমরা একটি ডাইনামিক সাইজ উইন্ডো মেইন্টেইন করবো, যেখানে ভ্যালু যোগ করতে থাকবো। মিন/ ম্যাক্স/ ইকুয়াল, কোন এক কন্ডিশন পেলে আমরা আমাদের মিনিমাম উইন্ডো সাইজ পেয়ে যাবো। প্রোগ্রাম এ কি চাওয়া হয়েছে তার উপরে ভিত্তি করে আমাদের কোড এ কন্ডিশন এর পরিবর্তন হবে। এখানে আমরা ১ম টেকনিক এর মত করে ইন্সার্ট করতে থাকবো এবং কন্ডিশন চেক করবো। আর এলেমেন্ট উইন্ডোতে আছে কিনা, উইন্ডো সাইজ কি আমাদের মূল অ্যারে থেকে বড় হয়ে গেলো কিনা - এসব আমরা ২য় টেকনিক এর মত একটি deque নিয়ে চেক করতে পারি।

৪র্থ টেকনিক (Fourth Technique):

আমরা এমন একটি উইন্ডো মেইন্টেইন করবো যা কিনা 1 to w সকল সংখ্যা যদি না পাই, উইন্ডো সাইজ বারাতে থাকবে, নাহলে সাইজ কমাতে থাকবে। আমরা মিনিমাম উইন্ডো সাইজের ট্র্যাক রাখবো। 1 to w সকল এলেমেন্ট পেয়ে গেলাম কিনা এটি আমরা নরমাল একটি ফ্রিকুয়েন্সি কাউন্টের মাধ্যমে করতে পারি। যখন সকল এলেমেন্ট এর কাউন্ট >0 হবে, তখন আমরা আমাদের মিনিমাম উইন্ডো সাইজ রিটার্ন করে দিবো।

প্র্যাক্টিস প্রব্লেম (Practice Problems): 

• Uva 1121 (Subsequence)
• Uva 11536 (Smallest-Sub-Array)
• LeetCode 239 (Sliding Window Maximum)
• HackerRank (The Maximum Subarray)
• Spoj (KOIREP - Representatives)
• Codeforces (Bear and Square Grid)