সমস্যা
মনে করুন একটি স্ট্রিং S আছে যেটি "abcdefghijklmnopqrstuvwxyz" স্ট্রিংয়ের অনন্ত র্যাপ-আরাউন্ড (infinite wraparound) সংস্করণ। অর্থাৎ S হবে:
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি স্ট্রিং str একমাত্র আর্গুমেন্ট হিসেবে নেবে।
ফাংশনটি বের করবে
str-র কতগুলো ইউনিক নন-эм্পটি সাবস্ট্রিংS-তে উপস্থিত।ফাংশনটি সেই সংখ্যাটি রিটার্ন করবে।
উদাহরণ:
const str = "zab";
আউটপুট হবে:
const output = 6;
আউটপুট ব্যাখ্যা
"zab" স্ট্রিংয়ের ছয়টি সাবস্ট্রিং "z", "a", "b", "za", "ab", "zab" স্ট্রিং S-তে আছে।
উদাহরণ
কোডটি নিচের মতো (DP):
const str = "zab"; const allSubstrings = (str = '') => { const dp = new Array(26).fill(0); dp[str.charCodeAt(0) - 97] = 1; maxCount = 1; for (let i = 1; i < str.length; i++) { if ((str.charCodeAt(i) - str.charCodeAt(i - 1) == 1) || (str.charCodeAt(i) - str.charCodeAt(i - 1) == -25)) { maxCount++; } else { maxCount = 1; } dp[str.charCodeAt(i) - 97] = Math.max(dp[str.charCodeAt(i) - 97], maxCount); } return dp.reduce((item, val) => { return val + item; }) }; console.log(allSubstrings(str)); আউটপুট
কনসোলে আউটপুট:
6
