Definition
- Vertical scan treats the string array like a grid with each string as a row, scanning column by column.
- Reference string is the first string in the array, and each of its character positions is compared against the same position in every other string.
- Early termination stops the scan the moment any string is shorter than the current position or shows a different character.
- Time complexity is O(S) where S is the total characters examined, which is at most the number of strings times the prefix length.
- Edge cases include an empty array (returns empty string) and any empty string (prefix is immediately empty).
The National Bank of India has a batch of account numbers that share a common branch prefix. A clerk wants the longest leading portion identical across all of them. The clerk reads the first character of every number: if they all match, keep it and move to the second character. The moment one number runs out of digits or shows a different character, the shared prefix ends right there.
Understanding the Concepts
What is the Longest Common Prefix problem?
The Longest Common Prefix problem finds the longest starting substring shared by every string in an array. If the input is ["flower", "flow", "flight"], the answer is "fl" because all three strings start with "fl" but disagree at the third character. This is a common interview problem that tests string traversal and edge-case handling.
package com.bank.dsa;
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String first = strs[0];
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return first.substring(0, i);
}
}
}
return first;
}
}
Why does this matter in banking?
At the National Bank of India, account numbers within a branch share a common prefix that identifies the branch and product type. When Rajesh processes a batch of transfers, he extracts the longest common prefix to identify which branch the batch belongs to. This helps route the batch to the correct processing center without examining every individual account.
package com.bank.service;
import com.bank.dsa.LongestCommonPrefix;
public class BatchRoutingService {
public String identifyBranch(String[] accountNumbers) {
String prefix = LongestCommonPrefix.longestCommonPrefix(accountNumbers);
System.out.println("Batch branch prefix: '" + prefix + "'");
return prefix;
}
public static void main(String[] args) {
String[] batch = {"HDFC0012345", "HDFC0012890", "HDFC0012001"};
new BatchRoutingService().identifyBranch(batch);
}
}
Batch branch prefix: 'HDFC0012'
How does vertical scan work step by step?
Vertical scan treats the strings like rows of a grid and reads down each column. Take the first string as the reference. For column index i, read the character at position i from the reference string, then check that every other string has the same character at position i. If any string is shorter than position i or has a different character, return the reference substring from 0 to i. If you reach the end of the reference string without any mismatch, the entire reference is the common prefix.
package com.bank.dsa;
public class VerticalScanDemo {
public static void main(String[] args) {
String[] accounts = {"ICICI001234", "ICICI001890", "ICICI002001"};
String first = accounts[0];
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
boolean allMatch = true;
for (int j = 1; j < accounts.length; j++) {
if (i >= accounts[j].length() || accounts[j].charAt(i) != c) {
allMatch = false;
break;
}
}
System.out.println("Column " + i + " char='" + c + "' allMatch=" + allMatch);
if (!allMatch) {
System.out.println("Prefix: '" + first.substring(0, i) + "'");
return;
}
}
System.out.println("Prefix: '" + first + "'");
}
}
Column 0 char='I' allMatch=true
Column 1 char='C' allMatch=true
Column 2 char='I' allMatch=true
Column 3 char='C' allMatch=true
Column 4 char='I' allMatch=true
Column 5 char='0' allMatch=true
Column 6 char='0' allMatch=true
Column 7 char='1' allMatch=false
Prefix: 'ICICI00'
What is the time and space complexity?
Time complexity is O(S) where S is the total number of character comparisons made. In the best case, when the first characters differ, only n comparisons are needed where n is the number of strings. In the worst case, when all strings are identical, S equals the total length of all strings. Space complexity is O(1) beyond the input, since no extra data structures are created.
package com.bank.dsa;
public class ComplexityDemo {
public static void main(String[] args) {
// Best case: first characters differ, only n comparisons
String[] bestCase = {"ABC", "DEF", "GHI"};
System.out.println(LongestCommonPrefix.longestCommonPrefix(bestCase)); // ""
// Worst case: all identical, examines every character
String[] worstCase = {"AAAA", "AAAA", "AAAA"};
System.out.println(LongestCommonPrefix.longestCommonPrefix(worstCase)); // "AAAA"
}
}
AAAA
What are the edge cases?
An empty array returns an empty string. A single-element array returns that string itself because it is trivially the common prefix. If any string in the array is empty, the common prefix is immediately empty because no character can match position 0 of an empty string.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println("Empty array: '" + LongestCommonPrefix.longestCommonPrefix(new String[]{}) + "'");
System.out.println("Single: '" + LongestCommonPrefix.longestCommonPrefix(new String[]{"HDFC"}) + "'");
System.out.println("Has empty: '" + LongestCommonPrefix.longestCommonPrefix(new String[]{"HDFC", "", "HDFC"}) + "'");
System.out.println("All same: '" + LongestCommonPrefix.longestCommonPrefix(new String[]{"NBI", "NBI", "NBI"}) + "'");
}
}
Empty array: ''
Single: 'HDFC'
Has empty: ''
All same: 'NBI'
How is vertical scan different from other approaches?
| Approach | How it works | Time | Space | Early exit |
|---|---|---|---|---|
| Vertical scan | Check column by column across all strings | O(S) | O(1) | Yes, at first mismatch |
| Horizontal scan | Fold prefix pairwise across strings | O(S) | O(m) | Less direct |
| Binary search | Binary search on prefix length, verify candidate | O(S log m) | O(1) | No |
| Trie | Insert all strings, walk single-child path | O(S) | O(S) | No |
package com.bank.dsa;
public class HorizontalScanDemo {
// Horizontal scan: fold prefix pairwise
public static String horizontalScan(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
public static void main(String[] args) {
String[] batch = {"HDFC0012345", "HDFC0012890", "HDFC0012001"};
System.out.println("Horizontal: " + horizontalScan(batch));
System.out.println("Vertical: " + LongestCommonPrefix.longestCommonPrefix(batch));
}
}
Horizontal: HDFC0012
Vertical: HDFC0012
What are common mistakes?
The first mistake is not handling the empty array or null input, which causes an ArrayIndexOutOfBoundsException. The second mistake is not checking whether a string is shorter than the current position before accessing its character, which causes a StringIndexOutOfBoundsException. The third mistake is using the wrong return value when the reference string is exhausted.
package com.bank.dsa;
public class CommonMistakesDemo {
// WRONG: no bounds check
public static String buggyPrefix(String[] strs) {
String first = strs[0]; // crashes on empty array
for (int i = 0; i < first.length(); i++) {
for (int j = 1; j < strs.length; j++) {
if (strs[j].charAt(i) != first.charAt(i)) { // crashes if strs[j] is shorter
return first.substring(0, i);
}
}
}
return first;
}
// CORRECT: guards null, empty, and length
public static void main(String[] args) {
String[] safe = {"HDFC001", "HDFC", "HDFC00123"};
System.out.println(LongestCommonPrefix.longestCommonPrefix(safe)); // "HDFC"
}
}
HDFC
What should a senior engineer know?
A senior engineer knows that vertical scan has the best early-exit behavior when prefixes are short, which is the common case for account numbers sharing a branch code. Horizontal scan is slightly less direct because it folds the prefix pairwise. Binary search on the prefix length has a log factor and is rarely needed. A trie is useful when you need to query the common prefix of different subsets repeatedly, but it uses O(S) extra space.
What are common interview follow-up questions?
- How would you find the longest common prefix of a subset of the array?
- Can you solve this with a Trie and what are the trade-offs?
- How would you adapt this for case-insensitive prefix matching?
- What if the input is a stream of strings arriving one at a time?
Visual Overview
Strings: "HDFC001" "HDFC012" "HDFC002"
Column 0: H H H ── all match
Column 1: D D D ── all match
Column 2: F F F ── all match
Column 3: C C C ── all match
Column 4: 0 0 0 ── all match
Column 5: 0 1 0 ── MISMATCH at string[1]
│
▼
return "HDFC0"
┌──────────────────────────────────┐
│ Vertical Scan Algorithm │
│ │
│ for each column i: │
│ c = first[i] │
│ for each string s: │
│ if i >= s.length ── STOP │
│ if s[i] != c ── STOP │
│ all match ── continue │
│ │
│ return first (all matched) │
└──────────────────────────────────┘
Key Takeaway
The Longest Common Prefix problem finds the longest starting substring shared by every string in an array, and vertical scan is the cleanest approach for it. Rajesh at the National Bank of India uses this to identify the common branch prefix in a batch of account numbers. The algorithm treats the strings like rows of a grid and scans down each column, comparing the character at each position across all strings and stopping at the first mismatch or at the end of any string.
The efficiency comes from early termination. When the shared prefix is short, which is typical for account numbers that differ after the branch code, the scan examines very few characters even if the strings are long. The worst case, where all strings are identical, examines every character exactly once per string, which is the total input size and is unavoidable.
Edge cases matter: an empty array returns an empty string, a single string is its own prefix, and any empty string in the array means the prefix is immediately empty. The most common bug is not checking whether a string is shorter than the current column index before accessing its character, which causes a StringIndexOutOfBoundsException.
Vertical scan has the best early-exit behavior among the common approaches. Horizontal scan folds the prefix pairwise but is less direct. Binary search on the prefix length adds a log factor. A trie gives O(S) time but uses O(S) extra space and is worth it only when you need to query the prefix of different subsets repeatedly.
Remember one sentence: scan each column across all strings, stop at the first mismatch or end, and return the reference substring up to that point.
---