Definition
- Encode and Decode Strings – design a reversible scheme to pack a list of arbitrary strings into one string and recover the exact list.
- Length-prefixing – each string is written as
length + separator + content, so decoding reads a count and then reads exactly that many characters. - Delimiter-safe – the content is never scanned for special characters, so no escaping is needed and no character is dangerous.
- Naive pitfall – joining with a delimiter like a comma fails when input strings contain that delimiter.
- Complexity – O(total content length) for both encoding and decoding.
National Bank of India must pack several free-text transaction remarks into a single wire message and unpack them perfectly on the other side. A naive packer glues remarks with a comma, but a remark might contain a comma and break everything. The reliable packer writes how many characters each remark has before the content, so the reader always knows exactly how far to read.
Understanding the Concepts
What is the Encode and Decode Strings problem?
The problem asks you to design two functions: encode takes a list of strings and returns a single string, and decode takes that single string and returns the original list. The scheme must work for any input, including strings that contain delimiters, special characters, and empty strings.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class EncodeDecodeStrings {
public static String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String s : strs) {
sb.append(s.length()).append('#').append(s);
}
return sb.toString();
}
public static List<String> decode(String encoded) {
List<String> result = new ArrayList<>();
int i = 0;
while (i < encoded.length()) {
int hashIdx = encoded.indexOf('#', i);
int len = Integer.parseInt(encoded.substring(i, hashIdx));
String str = encoded.substring(hashIdx + 1, hashIdx + 1 + len);
result.add(str);
i = hashIdx + 1 + len;
}
return result;
}
public static void main(String[] args) {
List<String> input = List.of("Rent", "EMI,HDFC", "", "Transfer#500");
String encoded = encode(input);
System.out.println("Encoded: " + encoded);
List<String> decoded = decode(encoded);
System.out.println("Decoded: " + decoded);
}
}
Encoded: 4#Rent8#EMI,HDFC0#12#Transfer#500
Decoded: [Rent, EMI,HDFC, , Transfer#500]
Why does the delimiter approach fail?
The tempting approach is to join strings with a delimiter like a comma and split on it when decoding. This fails when any input string contains that delimiter. Escaping the delimiter can patch it, but escaping is error-prone and bloats the output.
package com.bank.core;
import java.util.List;
public class DelimiterFails {
public static void main(String[] args) {
List<String> remarks = List.of("Rent", "EMI,HDFC", "Transfer");
// Naive join with comma
String joined = String.join(",", remarks);
System.out.println("Joined: " + joined);
// Split produces 4 parts instead of 3
String[] parts = joined.split(",");
System.out.println("Parts count: " + parts.length);
for (String p : parts) {
System.out.println(" '" + p + "'");
}
}
}
Joined: Rent,EMI,HDFC,Transfer
Parts count: 4
'Rent'
'EMI'
'HDFC'
'Transfer'
How does length-prefixing work?
For encoding, you process each string in order. Compute its length, write that length as digits, write a non-numeric separator (like #), then write the raw string content exactly as-is. The crucial property is that the string content is never scanned for special characters.
For decoding, keep a read cursor at the start. Read digits until you hit the separator to get the length. Skip the separator. Read exactly that many characters as the next string. Advance the cursor and repeat.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class LengthPrefixExplained {
public static void main(String[] args) {
// Encoding step by step
String s1 = "EMI";
String s2 = "Rs.12,500";
String encoded = s1.length() + "#" + s1 + s2.length() + "#" + s2;
System.out.println("Encoded: " + encoded);
// Decoding step by step
List<String> decoded = new ArrayList<>();
int cursor = 0;
while (cursor < encoded.length()) {
int hash = encoded.indexOf('#', cursor);
int len = Integer.parseInt(encoded.substring(cursor, hash));
String value = encoded.substring(hash + 1, hash + 1 + len);
decoded.add(value);
cursor = hash + 1 + len;
}
System.out.println("Decoded: " + decoded);
}
}
Encoded: 3#EMI9#Rs.12,500
Decoded: [EMI, Rs.12,500]
Why is the separator between length and content unambiguous?
When decoding, you only interpret characters as the length while you are in the digit-reading phase, which stops at the first separator. Once you switch to reading content by count, you never look for a separator. A separator inside the content is just data. The count tells you exactly when content ends, so you re-enter the digit phase only at the right boundary.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class SeparatorInContent {
public static String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String s : strs) sb.append(s.length()).append('#').append(s);
return sb.toString();
}
public static List<String> decode(String encoded) {
List<String> result = new ArrayList<>();
int i = 0;
while (i < encoded.length()) {
int h = encoded.indexOf('#', i);
int len = Integer.parseInt(encoded.substring(i, h));
result.add(encoded.substring(h + 1, h + 1 + len));
i = h + 1 + len;
}
return result;
}
public static void main(String[] args) {
// Content contains the separator character '#'
List<String> input = List.of("A#B", "C##D", "plain");
String enc = encode(input);
System.out.println("Encoded: " + enc);
System.out.println("Decoded: " + decode(enc));
}
}
Encoded: 3#A#B4#C##D5#plain
Decoded: [A#B, C##D, plain]
How do you handle empty strings?
An empty string has length zero, so it encodes as 0# (the digit zero, the separator, and no content). Decoding reads zero as the length, skips the separator, reads zero characters, and recovers the empty string.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class EmptyStringHandling {
public static String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String s : strs) sb.append(s.length()).append('#').append(s);
return sb.toString();
}
public static List<String> decode(String encoded) {
List<String> result = new ArrayList<>();
int i = 0;
while (i < encoded.length()) {
int h = encoded.indexOf('#', i);
int len = Integer.parseInt(encoded.substring(i, h));
result.add(encoded.substring(h + 1, h + 1 + len));
i = h + 1 + len;
}
return result;
}
public static void main(String[] args) {
List<String> input = List.of("", "hello", "", "");
String enc = encode(input);
System.out.println("Encoded: '" + enc + "'");
System.out.println("Decoded: " + decode(enc));
}
}
Encoded: '0#5#hello0#0#'
Decoded: [, hello, , ]
What about Unicode and multi-byte characters?
For Unicode, you must define length consistently. If you use String.length(), you count Java char units (UTF-16). If you encode to bytes with UTF-8, use the byte length instead. The encoder and decoder must agree on the unit and charset.
package com.bank.core;
import java.nio.charset.StandardCharsets;
public class UnicodeLengthHandling {
public static void main(String[] args) {
String hindi = "\u0930\u093E\u091C\u0947\u0936"; // Rajesh in Hindi
System.out.println("String: " + hindi);
System.out.println("char length: " + hindi.length());
System.out.println("UTF-8 byte length: " + hindi.getBytes(StandardCharsets.UTF_8).length);
}
}
String: राजेश
char length: 5
UTF-8 byte length: 15
What is the time and space complexity?
Encoding iterates each string once and appends the length prefix, so the total time is O(total content length). Decoding reads the encoded string once with a cursor, also O(total content length). Space is O(total content length) for the encoded string plus the output list.
What is the banking use case?
At National Bank of India, Rajesh batches free-text transaction remarks into a single payload transmitted between microservices. Remarks can contain any character including commas, pipes, and hash symbols. The length-prefixed scheme guarantees perfect round-trip reconstruction regardless of the content.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class RemarkSerializer {
public static String encodeRemarks(List<String> remarks) {
StringBuilder sb = new StringBuilder();
for (String r : remarks) sb.append(r.length()).append('#').append(r);
return sb.toString();
}
public static List<String> decodeRemarks(String wire) {
List<String> remarks = new ArrayList<>();
int i = 0;
while (i < wire.length()) {
int h = wire.indexOf('#', i);
int len = Integer.parseInt(wire.substring(i, h));
remarks.add(wire.substring(h + 1, h + 1 + len));
i = h + 1 + len;
}
return remarks;
}
public static void main(String[] args) {
List<String> remarks = List.of(
"EMI payment for Loan #A2024",
"Rs.12,500 transferred to Priya",
""
);
String wire = encodeRemarks(remarks);
System.out.println("Wire: " + wire);
System.out.println("Recovered: " + decodeRemarks(wire));
}
}
Wire: 27#EMI payment for Loan #A202430#Rs.12,500 transferred to Priya0#
Recovered: [EMI payment for Loan #A2024, Rs.12,500 transferred to Priya, ]
What are common interview follow-up questions?
Interviewers may ask about alternative encoding schemes, handling very large strings, or how to make the format extensible. Common follow-ups include:
- What if the length itself is very large? The digit prefix still works because you read digits until the separator.
- What about null strings? Define a convention, like length -1 for null, and handle it in both encode and decode.
- How does this compare to JSON or Protocol Buffers? Length-prefixing is simpler and faster for flat lists but lacks schema support for nested structures.
Visual Overview
Length-Prefixed Encoding ════════════════════════ Input: ["Rent", "EMI,HDFC", ""] Encode: ┌──────────┬──────────────┬────────┐ │ 4#Rent │ 8#EMI,HDFC │ 0# │ └──────────┴──────────────┴────────┘ Output: "4#Rent8#EMI,HDFC0#" Decode: cursor=0 → read "4" → skip # → read 4 chars "Rent" cursor=6 → read "8" → skip # → read 8 chars "EMI,HDFC" cursor=16 → read "0" → skip # → read 0 chars "" Done!
Key Takeaway
Encode and Decode Strings is about designing a reversible scheme to pack a list of arbitrary strings into one string and parse it back exactly, even when strings contain any character. The naive join-on-delimiter approach breaks when an input contains the delimiter, so the robust solution is length-prefixing: before each string, write its length, a separator, then the raw content untouched.
Decoding mirrors encoding: read digits until the separator to get the length, skip the separator, read exactly that many characters as the next string, and repeat. The count tells you where content ends, so a separator or comma inside the content is just data, never a boundary. Empty strings encode as length zero with no content, and Unicode requires consistent length units (characters or bytes) on both sides.
In the banking project at National Bank of India, Rajesh batches free-text transaction remarks for Priya into a single wire payload between microservices and reconstructs the exact list on the other side, even when remarks contain commas, pipes, or hash characters.
Remember one sentence: prefix each string with its length and a separator, so decoding reads by count and no character is ever special.
---