Encode and Decode Strings - Practice Coding Problems

Encode and Decode Strings - Problem

Design an algorithm to encode a list of strings to a single string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) { // ... your code return encoded_string; }

Machine 2 (receiver) has the function:

vector<string> decode(string s) { //... your code return strs; }

So Machine 1 does: string encoded_string = encode(strs);

And Machine 2 does: vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods. You are not allowed to solve the problem using any serialize methods (such as eval).

Input & Output

Example 1 — Basic Strings

$ Input: strs = ["hello", "world"]

› Output: ["hello", "world"]

💡 Note: Encode to "5#hello5#world", decode reads length 5, extracts "hello", reads length 5, extracts "world"

Example 2 — Empty String

$ Input: strs = ["", "a"]

› Output: ["", "a"]

💡 Note: Encode to "0#1#a", decode reads length 0 for empty string, then length 1 for "a"

Example 3 — Special Characters

$ Input: strs = ["a|b", "c#d"]

› Output: ["a|b", "c#d"]

💡 Note: Encode to "3#a|b3#c#d", length prefix handles strings with delimiters correctly

Constraints

1 ≤ strs.length ≤ 200
0 ≤ strs[i].length ≤ 200
strs[i] contains any possible characters out of 256 valid ASCII characters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings that need to be encoded

Encode

Convert array to single string with length prefixes

Decode

Reconstruct original array from encoded string

Key Takeaway

🎯 Key Insight: Length prefixes eliminate the need for escaping special characters in strings

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is using length prefixes to eliminate delimiter ambiguity. Best approach is length-prefixed encoding where each string is preceded by its length and a delimiter. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Length-Prefixed Encoding	O(n)	O(1)	Prefix each string with its length to avoid delimiter conflicts
Simple Delimiter Approach	O(n)	O(1)	Use a delimiter character to separate strings

Length-Prefixed Encoding — Algorithm Steps

For each string, prepend its length and a delimiter
Concatenate all length-prefixed strings
During decode, read length first, then extract exact number of characters

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Length Prefix

Prepend each string with its length

Concatenate

Join all length-prefixed strings

Parse by Length

Read length, then extract exact characters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* encode(char** strs, int strsSize) {
    if (strsSize == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    int totalLen = 0;
    for (int i = 0; i < strsSize; i++) {
        int len = strlen(strs[i]);
        totalLen += len + 10; // extra space for length prefix
    }
    
    char* result = malloc(totalLen + 1);
    result[0] = '\0';
    
    for (int i = 0; i < strsSize; i++) {
        char lengthStr[10];
        sprintf(lengthStr, "%d#", (int)strlen(strs[i]));
        strcat(result, lengthStr);
        strcat(result, strs[i]);
    }
    
    return result;
}

char** decode(char* s, int* returnSize) {
    if (strlen(s) == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    char** result = malloc(1000 * sizeof(char*));
    *returnSize = 0;
    
    int i = 0;
    int sLen = strlen(s);
    
    while (i < sLen) {
        // Find delimiter
        int delimiterPos = i;
        while (delimiterPos < sLen && s[delimiterPos] != '#') {
            delimiterPos++;
        }
        
        // Extract length
        char lengthStr[10];
        strncpy(lengthStr, s + i, delimiterPos - i);
        lengthStr[delimiterPos - i] = '\0';
        int length = atoi(lengthStr);
        
        // Extract string
        int stringStart = delimiterPos + 1;
        result[*returnSize] = malloc(length + 1);
        strncpy(result[*returnSize], s + stringStart, length);
        result[*returnSize][length] = '\0';
        (*returnSize)++;
        
        i = stringStart + length;
    }
    
    return result;
}

char** solution(char** strs, int strsSize, int* returnSize) {
    char* encoded = encode(strs, strsSize);
    char** decoded = decode(encoded, returnSize);
    free(encoded);
    return decoded;
}

int main() {
    // Simplified input parsing for C
    char** strs = malloc(100 * sizeof(char*));
    int strsSize = 0;
    
    // For demo: hardcode test case
    strs[0] = "hello";
    strs[1] = "world";
    strsSize = 2;
    
    int returnSize;
    char** result = solution(strs, strsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all characters in all strings for encoding and decoding

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for length calculations and parsing

✓ Linear Space

35.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Length-Prefixed Encoding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler