Day 6 : Blind 75

Hey everyone!

I’m back with Day 6. One thing I’ve realized recently is that if you have a solid grasp of Sets, Heaps, and Hashing, you’re already halfway there. Most LeetCode logic relies on these fundamentals; the rest is just a bit of creative tweaking!

Initially, I’ll be honest: I struggled to wrap my head around some of these. But as the difficulty increases, I can feel my logical thinking and problem-solving skills leveling up. Let’s dive into today’s challenge!

The Problem: Encode and Decode Strings

The goal is to take a list of strings and transform them into a single, continuous string. This “encoded” string must be robust enough to be perfectly reversed back into the original list, no matter what characters the original strings contain.

1. The Brute-Force Approach A common first instinct is to join the strings using a simple delimiter, like a hash (#) or a slash (/).

• The Flaw: This method is risky. If any of your input strings actually contain that delimiter (e.g., the word “Hash#Tag”), the decoder will get confused and split the string in the wrong place, breaking your logic.

2. The Optimal Solution: Length-Prefixed Encoding

To avoid ambiguity, we use a Chunk-Based strategy. Instead of just a delimiter, we prefix each string with its own length.

• How Encoding Works: Iterate through the list. For every word, calculate its length and append it to a StringBuilder, followed by a specific delimiter (like #) and then the string itself.
• Example: ["hello", "world"] becomes "5#hello5#world".
• How Decoding Works: Use a two-pointer approach. One pointer identifies the delimiter to determine the length of the upcoming word. The second pointer then uses that length to “jump” ahead and extract the exact number of characters.
• Collision Proof: It doesn’t matter if your string contains #, $, or !; the length prefix tells the decoder exactly when to stop.
• Efficiency: It runs in O(n) time complexity, as you only traverse the data once during both encoding and decoding.

Pro-Tip: This is a LeetCode Premium problem. If you don’t have a subscription, you can practice it for free on NeetCode, which is where I’ve been solving mine!

Progress Update: 69 to go! We only have two questions left in the “Array and Hashing” category of the Blind 75. Once I finish those, I’m planning to write a summary of the key patterns and approaches we’ve used so far as a quick revision guide.

Stay tuned!