ধরুন আমাদের একটি স্ট্রিং, পাসওয়ার্ড আছে। আমাদের পাসওয়ার্ড শক্তিশালী করার জন্য প্রয়োজনীয় ন্যূনতম পরিবর্তনগুলি খুঁজে বের করতে হবে। তাই পাসওয়ার্ডের কিছু নিম্নোক্ত মানদণ্ড রয়েছে -
- এটি কমপক্ষে 6 অক্ষর দীর্ঘ এবং সর্বাধিক 20-অক্ষর দীর্ঘ হতে হবে
- এতে কমপক্ষে একটি ছোট হাতের অক্ষর, কমপক্ষে একটি বড় হাতের অক্ষর এবং কমপক্ষে একটি সংখ্যাসূচক অক্ষর থাকতে হবে৷
- এতে অবশ্যই একটি সারিতে তিনটি পুনরাবৃত্তি করা অক্ষর থাকবে না যেমন …aaa…, …PPP…, …888….
তাই যদি ইনপুটটি "aa26bbb" এর মত হয়, তাহলে আমাদের অন্তত একটি পরিবর্তন প্রয়োজন, যেহেতু এখানে কোনো বড় হাতের অক্ষর নেই, এবং একটি সারিতে তিনটি b আছে, তাই আমরা এটিকে শক্তিশালী করতে একটি বড় হাতের অক্ষর দিয়ে যেকোনো b প্রতিস্থাপন করতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- অনুপস্থিত প্রকার সেট করুন :=3।
- যদি এটিতে অন্তত একটি ছোট হাতের অক্ষর থাকে, অনুপস্থিত প্রকারগুলি 1 দ্বারা হ্রাস করুন
- যদি এটিতে অন্তত একটি বড় হাতের অক্ষর থাকে, তাহলে অনুপস্থিত প্রকারগুলি 1 দ্বারা হ্রাস করুন
- যদি এটিতে কমপক্ষে একটি নম্বর থাকে, অনুপস্থিত প্রকারগুলি 1 দ্বারা হ্রাস করুন
- পরিবর্তন :=0, এক :=0 এবং দুই :=0, p :=2
- যখন p
- যদি s[p] s[p – 1] এর মতো হয় এবং এটিও s[p - 2] এর মতো হয়, তাহলে
- দৈর্ঘ্য :=2
- যখন p
- দৈর্ঘ্য :=দৈর্ঘ্য + 1
- p :=p + 1
- পরিবর্তন :=পরিবর্তন + দৈর্ঘ্য / 3
- যদি দৈর্ঘ্য 3 দ্বারা বিভাজ্য হয়, তাহলে 1 দ্বারা একটি বাড়ান
- অন্যথায় যখন দৈর্ঘ্য 3 দ্বারা বিভাজ্য, তখন 1 দ্বারা দুই বাড়ান
- যদি s[p] s[p – 1] এর মতো হয় এবং এটিও s[p - 2] এর মতো হয়, তাহলে
- মুছুন :=s – 20 এর আকার
- পরিবর্তন :=পরিবর্তন - ন্যূনতম মুছে ফেলা এবং একটি
- পরিবর্তন :=পরিবর্তন - (সর্বাধিক (মোছার সর্বোচ্চ - এক এবং 0) এবং দুটি * 2)/2
- পরিবর্তন :=পরিবর্তন - (মোছার সর্বোচ্চ - এক - 2 * দুই এবং 0)/2
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution(object): def strongPasswordChecker(self, s): missing_type = 3 if any('a' <= c <= 'z' for c in s): missing_type -= 1 if any('A' <= c <= 'Z' for c in s): missing_type -= 1 if any(c.isdigit() for c in s): missing_type -= 1 change = 0 one = two = 0 p = 2 while p < len(s): if s[p] == s[p-1] == s[p-2]: length = 2 while p < len(s) and s[p] == s[p-1]: length += 1 p += 1 change += length / 3 if length % 3 == 0: one += 1 elif length % 3 == 1: two += 1 else: p += 1 if len(s) < 6: return max(missing_type, 6 - len(s)) elif len(s) <= 20: return max(missing_type, change) else: delete = len(s) - 20 change -= min(delete, one) change -= min(max(delete - one, 0), two * 2) / 2 change -= max(delete - one - 2 * two, 0) / 3 return delete + max(missing_type, change) ob = Solution() print(ob.strongPasswordChecker('aa26bbb'))
ইনপুট
“aa26bbb”
আউটপুট
1