The Hidden Island

ধরি, আমাদের "?" আছে X টা। আমরা একটা লিস্ট L রাখব যেখানে শুরুতে (K - X) টা হারানো অক্ষর রাখব। হারানো অক্ষর লিস্টে বর্ণানুক্রমে রাখব।

আমরা একটা ফাকা স্ট্রিং R নিই। S স্ট্রিং টির আমরা বাম থেকে ডানে যেতে থাকি। যখনই S স্ট্রিং টিতে আমরা একটা ইংরেজি অক্ষর পাব, আমরা সেটা R এ যোগ করে দিব।
যদি "?" পাই, তাহলে হারানো অক্ষর থেকে L লিস্টে একটি অক্ষর যোগ করে দিব।

এখন "?" এ অবশ্যই একটি অক্ষর বসবে, তাই আমরা লিস্ট সবচেয়ে ছোট অক্ষরটি R এ বসাব। এখন আমরা লিস্ট থেকে আরও কিছু অক্ষর বসাতে পারি R এ। তবে সেটি নির্ভর করে "?" এর পরের অক্ষরটি কি তার উপর ।

ধরি, "?" এর পরের অক্ষরটি 'D'. তাহলে বর্ণানুক্রমে ছোট স্ট্রিং বানানর জন্য আমাদের উচিত লিস্টে থাকা 'D' এর চেয়ে ছোট সবগুলো অক্ষর R এ যোগ করা।
'D' এর চেয়ে বড় কিছু আমাদের স্ট্রিং এর এ পর্যায়ে যোগ করা ঠিক না। কারণ এর চেয়ে পরের 'D' টি নিয়েই আমরা বর্ণানুক্রমে ছোট পেতে পারি।

আমাদের লিস্টে যদি কিছু 'D' থাকে, সেটা যোগ করব কিনা, সেটা দেখা যাক।

ধরি, স্ট্রিংটি হল ?DDA... । আমরা অবশ্যই একটি অক্ষর বসানোর নিয়মটি এখন ভুলে যাই। যদি প্রথম ? এ আমরা 'D' বসাই তাহলে আমরা পাব, DDDA.... । যদি প্রথমে না বসাই, পাব DDA.... । দ্বিতীয়টি বর্ণানুক্রমে ছোট।
আবার ধরি, স্ট্রিংটি হল ?DDE... । যদি প্রথম ? এ আমরা 'D' বসাই তাহলে আমরা পাব, DDDE... । যদি প্রথমে না বসাই, পাব DDE.... । প্রথমটি বর্ণানুক্রমে ছোট।
তাই আমাদের ? এর পরে এমন 'D' ব্যতীত প্রথম অক্ষর জানতে হবে। অক্ষর ছোট হলে, এখন না বসানো শ্রেয়। বড় হলে, এখনই 'D' বসানো শ্রেয়।

এটি আমরা একটি লুপ দিয়েই করতে পারি।

Time Complexity: O(|S| + K)

Subtask 1:

হারানো অক্ষরগুলোতে সর্ট করে নেই। এখন আমরা ? পজিশন গুলোতে বাম থেকে ডানে এক বা একাধিক হারানো অক্ষর বসিয়ে সব ধরনের স্ট্রিং বানানর চেষ্টা করি। স্ট্রিং গুলোর মধ্যে সবচেয়ে ছোটটিই বেছে নিলেই হবে।

Time Complexity: O(|S| * ( 2^10) )

Subtask 2:

আমরা Dynamic Programming দিয়ে এটি সমাধান করতে পারি। স্টেট হিসেবে আমরা রাখব স্ট্রিং S এর পজিশন এবং K থেকে কতগুলো অক্ষর ব্যবহার করেছি। এতে আমরা প্রতিটি |S| * K টি স্টেট এর জন্য স্ট্রিং বানিয়ে ফেলতে পারি।

Time Complexity: O(|S| * K * |S|)