Skip to content

Encode and Decode Strings

Encode and Decode Strings

Medium Day 12 • Striver Blind 75

📌 Problem Overview

Design an algorithm to encode a list of strings to a single string, and decode it back.

Examples & Constraints

Example 1:

Input: strs = ["leet","code","love","you"]
Output: ["leet","code","love","you"]

Constraints:

0 <= strs.length <= 200

💡 Approach & Intuition

Prefix each string with length and a delimiter (e.g., 4#leet4#code).

🎯 Pattern Recognition

Length Prefix Framing

📊 Step-by-Step Execution (Mermaid Diagram)

graph TD
    Start["Input Data"] --> Process["Process Element by Element"]
    Process --> Lookup{"Hash Map / Set Lookup"}
    Lookup -- "Match Found" --> Return["Return Indices / Result"]
    Lookup -- "No Match" --> Store["Store in Map / Set"]
    Store --> Process

🐢 Brute Force Solution

Code

function encode(strs) {
  return strs.map(s => s.length + '#' + s).join('');
}
function decode(s) {
  const res = [];
  let i = 0;
  while (i < s.length) {
    let j = s.indexOf('#', i);
    let len = parseInt(s.substring(i, j));
    res.push(s.substring(j + 1, j + 1 + len));
    i = j + 1 + len;
  }
  return res;
}
function encodeDecode(strs) {
  return decode(encode(strs));
}

Time Complexity: O(N)
Space Complexity: O(N)
Explanation: Length-delimited framing.

⚡ Optimized Solution

Code

function encode(strs) {
  return strs.map(s => s.length + '#' + s).join('');
}
function decode(s) {
  const res = [];
  let i = 0;
  while (i < s.length) {
    let j = s.indexOf('#', i);
    let len = parseInt(s.substring(i, j));
    res.push(s.substring(j + 1, j + 1 + len));
    i = j + 1 + len;
  }
  return res;
}
function encodeDecode(strs) {
  return decode(encode(strs));
}

Time Complexity: O(N)
Space Complexity: O(N)
Explanation: Chunk length prefix encoding.

🐾 Step-by-Step Walkthrough

Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
Iterate & Evaluate: Process the input according to the boundary conditions.
Update & Return: Compute the optimal answer and return early or at termination.

🎙️ FAANG Interview Pitch

Prefixing length before delimiter makes parsing unambiguous regardless of internal string characters.

💡 Progressive Hints

Format each string as length + ’#’ + string.

⚡ Interactive Practice

👉 Solve this problem interactively in the DSA Lab