encode-decode-strings.ts

/**
 * 271. Encode and Decode Strings  (Medium)
 * Link: https://leetcode.com/problems/encode-and-decode-strings/
 * (LeetCode Premium — problem statement is well known.)
 *
 * Design encode/decode so a list of strings can be serialized to a single
 * string and recovered exactly. Strings may contain any characters (including
 * the delimiter and digits), so a naive separator does not work.
 *
 * Example:
 *   encode(["lint", "code"]) -> "4#lint4#code"
 *   decode("4#lint4#code")   -> ["lint", "code"]
 *
 * Approach:
 *   Length-prefix framing. Encode each string as `<length>#<string>`. To decode,
 *   read digits up to the '#', parse the length, then slice exactly that many
 *   characters — so the content is never confused with the delimiter.
 *
 * Time:  O(total characters) for both directions.
 * Space: O(total characters)
 */
export function encode(strs: string[]): string {
  let out = "";
  for (const s of strs) {
    out += `${s.length}#${s}`;
  }
  return out;
}

export function decode(s: string): string[] {
  const result: string[] = [];
  let i = 0;

  while (i < s.length) {
    let j = i;
    while (s[j] !== "#") j++; // read the length digits
    const length = Number(s.slice(i, j));
    const start = j + 1;
    result.push(s.slice(start, start + length));
    i = start + length;
  }

  return result;
}