Longest Substring with At Least K Repeating Characters

🚀 Day 81/100 – 𝐋𝐨𝐧𝐠𝐞𝐬𝐭 𝐒𝐮𝐛𝐬𝐭𝐫𝐢𝐧𝐠 𝐰𝐢𝐭𝐡 𝐀𝐭 𝐋𝐞𝐚𝐬𝐭 𝐊 𝐑𝐞𝐩𝐞𝐚𝐭𝐢𝐧𝐠 𝐂𝐡𝐚𝐫𝐚𝐜𝐭𝐞𝐫𝐬 Today’s problem was a bit tricky but super interesting — Longest Substring with At Least K Repeating Characters. 🔍 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠: This problem can be efficiently solved using a 𝐃𝐢𝐯𝐢𝐝𝐞 & 𝐂𝐨𝐧𝐪𝐮𝐞𝐫 𝐚𝐩𝐩𝐫𝐨𝐚𝐜𝐡 instead of brute force. 💡 𝐂𝐨𝐫𝐞 𝐈𝐝𝐞𝐚: Count frequency of all characters If any character appears less than k, it cannot be part of the valid substring Split the string at that character and solve recursively ⚡ 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: Count 𝐟𝐫𝐞𝐪𝐮𝐞𝐧𝐜𝐲 𝐨𝐟 𝐜𝐡𝐚𝐫𝐚𝐜𝐭𝐞𝐫𝐬 Traverse string: If any char frequency < k → split Recursively solve 𝐥𝐞𝐟𝐭 & 𝐫𝐢𝐠𝐡𝐭 parts Return max of both ⏱️ 𝐓𝐢𝐦𝐞 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲: ~O(n log n) (depends on splits) 📦 𝐒𝐩𝐚𝐜𝐞 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲: O(n) (recursion stack) #Day81 #100DaysOfCode #Java #DSA #LeetCode #DivideAndConquer #CodingJourney

  • graphical user interface, text

To view or add a comment, sign in

Explore content categories