Example 1: ["flower", "flow", "flight"]
LCP: "fl"
Explanation: "fl" is the longest string that starts every word
 
Example 2: ["dog", "racecar", "car"]
LCP: ""
Explanation: No common prefix exists
 
Example 3: ["interview", "internal", "internet", "interleave"]
LCP: "inter"
Explanation: All words share "inter" at the start
 
Example 4: ["", "hello", "help"]
LCP: ""
Explanation: Empty string means no common prefix
 
Example 5: ["test"]
LCP: "test"
Explanation: Single string is its own LCP
 
Example 6: ["a", "a", "a"]
LCP: "a"
Explanation: Identical strings yield the full string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

def longest_common_prefix_horizontal(strs: list[str]) -> str:
    """
    Horizontal Scanning approach for Longest Common Prefix.
    
    Time Complexity: O(S) where S = sum of all string lengths
                     In worst case, we compare all characters
    Space Complexity: O(1) - only using constant extra space
    
    Best for: General purpose, when you have no prior knowledge about the strings
    """
    if not strs:
        return ""
    
    # Start with the first string as the candidate prefix
    prefix = strs[0]
    
    for i in range(1, len(strs)):
        # Shrink prefix until current string starts with it
        while not strs[i].startswith(prefix):
            prefix = prefix[:-1]  # Remove last character
            if not prefix:
                return ""  # No common prefix exists
    
    return prefix
 
 
# Detailed trace for ["flower", "flow", "flight"]:
# 
# Initial: prefix = "flower"
# 
# i=1, strs[1]="flow":
#   "flow".startswith("flower")? No
#   prefix = "flowe"
#   "flow".startswith("flowe")? No
#   prefix = "flow"
#   "flow".startswith("flow")? Yes ✓
# 
# i=2, strs[2]="flight":
#   "flight".startswith("flow")? No
#   prefix = "flo"
#   "flight".startswith("flo")? No
#   prefix = "fl"
#   "flight".startswith("fl")? Yes ✓
# 
# Return "fl"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

def longest_common_prefix_vertical(strs: list[str]) -> str:
    """
    Vertical Scanning approach for Longest Common Prefix.
    
    Time Complexity: O(S) where S = sum of all string lengths
                     But terminates early when LCP is found
    Space Complexity: O(1)
    
    Best for: When the LCP is expected to be short
              Terminates as soon as mismatch is found
    """
    if not strs:
        return ""
    
    # Compare character-by-character across all strings
    for i in range(len(strs[0])):
        char = strs[0][i]
        
        for j in range(1, len(strs)):
            # Check if current position exceeds string length
            # or if characters don't match
            if i >= len(strs[j]) or strs[j][i] != char:
                return strs[0][:i]
    
    # All characters of first string matched in all strings
    return strs[0]
 
 
# Alternative with explicit loop (more educational):
def longest_common_prefix_vertical_explicit(strs: list[str]) -> str:
    """
    More explicit version showing the column-by-column comparison.
    """
    if not strs:
        return ""
    if len(strs) == 1:
        return strs[0]
    
    min_len = min(len(s) for s in strs)
    
    # Check each column
    for col in range(min_len):
        # All strings must have the same character in this column
        reference_char = strs[0][col]
        
        for row in range(1, len(strs)):
            if strs[row][col] != reference_char:
                # Mismatch found - return prefix up to (but not including) this column
                return strs[0][:col]
    
    # All columns matched up to min_len
    return strs[0][:min_len]
 
 
# Visual: Vertical Scanning
#
#     Column:  0   1   2   3   4   5
#   ┌─────────────────────────────────────
# String 0: │ f │ l │ o │ w │ e │ r │
#   ├─────────────────────────────────────
# String 1: │ f │ l │ o │ w │   │   │
#   ├─────────────────────────────────────
# String 2: │ f │ l │ i │ g │ h │ t │
#   └─────────────────────────────────────
#             ↓   ↓   ↓
#            ✓   ✓   ✗ (mismatch at column 2)
#
# Return strs[0][:2] = "fl"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

def longest_common_prefix_divide_conquer(strs: list[str]) -> str:
    """
    Divide and Conquer approach for Longest Common Prefix.
    
    Time Complexity: O(S) where S = sum of all string lengths
                     T(n) = 2T(n/2) + O(m), solves to O(S)
    Space Complexity: O(n log n) for recursion stack
                      (depth log n, each level may store prefix)
    
    Best for: Parallelizable scenarios, distributed computing
              Each subproblem can be solved independently
    """
    if not strs:
        return ""
    
    def lcp_two_strings(s1: str, s2: str) -> str:
        """Find LCP of exactly two strings."""
        min_len = min(len(s1), len(s2))
        for i in range(min_len):
            if s1[i] != s2[i]:
                return s1[:i]
        return s1[:min_len]
    
    def divide_conquer(left: int, right: int) -> str:
        """Recursively find LCP of strs[left:right+1]."""
        # Base case: single string
        if left == right:
            return strs[left]
        
        # Divide: split into two halves
        mid = (left + right) // 2
        
        # Conquer: solve each half recursively
        lcp_left = divide_conquer(left, mid)
        lcp_right = divide_conquer(mid + 1, right)
        
        # Combine: find LCP of the two results
        return lcp_two_strings(lcp_left, lcp_right)
    
    return divide_conquer(0, len(strs) - 1)
 
 
# Recursion tree for ["flower", "flow", "flight", "fly"]:
#
#                    LCP(0,3)
#                   /        \
#              LCP(0,1)     LCP(2,3)
#              /     \      /     \
#         "flower"  "flow" "flight" "fly"
#              \     /      \     /
#             "flow"        "fl"
#                  \        /
#                   \      /
#                    "fl"
#
# Work at each level:
# Level 2: Compare pairs → 4 strings examined
# Level 1: LCP("flow","flow") → "flow", LCP("flight","fly") → "fl"  
# Level 0: LCP("flow","fl") → "fl"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

def longest_common_prefix_binary_search(strs: list[str]) -> str:
    """
    Binary Search approach for Longest Common Prefix.
    
    Time Complexity: O(S × log m) where m = min string length, S = total chars
                     log m binary search iterations
                     Each iteration checks O(n × mid) characters
    Space Complexity: O(1)
    
    Best for: Unique interview approach, demonstrating binary search thinking
    Note: Often less efficient than vertical scanning in practice
    """
    if not strs:
        return ""
    
    # Find the minimum length string - LCP cannot be longer
    min_len = min(len(s) for s in strs)
    
    # Binary search on the length of the prefix
    left, right = 0, min_len
    
    def is_common_prefix(length: int) -> bool:
        """Check if strs[0][:length] is a prefix of all strings."""
        prefix = strs[0][:length]
        return all(s.startswith(prefix) for s in strs)
    
    while left <= right:
        mid = (left + right) // 2
        
        if is_common_prefix(mid):
            # This length works, try longer
            left = mid + 1
        else:
            # This length doesn't work, try shorter
            right = mid - 1
    
    # 'right' is the longest valid prefix length
    return strs[0][:right] if right >= 0 else ""
 
 
# More efficient version avoiding repeated string slicing:
def longest_common_prefix_binary_search_optimized(strs: list[str]) -> str:
    """
    Optimized binary search that compares characters directly.
    """
    if not strs:
        return ""
    
    min_len = min(len(s) for s in strs)
    if min_len == 0:
        return ""
    
    left, right = 0, min_len - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Check if all strings match strs[0] at positions [0, mid]
        all_match = True
        for s in strs:
            # Check character at position mid
            # (assumes all previous positions already checked in earlier iterations)
            if s[mid] != strs[0][mid]:
                all_match = False
                break
        
        # Actually need to verify entire prefix, not just one character
        # Let's fix this:
        all_match = True
        for s in strs[1:]:
            for i in range(mid + 1):
                if s[i] != strs[0][i]:
                    all_match = False
                    break
            if not all_match:
                break
        
        if all_match:
            left = mid + 1
        else:
            right = mid - 1
    
    return strs[0][:right + 1] if right >= 0 else ""
 
 
# Binary Search Visualization:
#
# strs = ["flower", "flow", "flight"]
# min_len = 4 (length of "flow")
#
# Binary search on length [0, 4]:
#
#   left=0, right=4, mid=2
#   Is "fl" prefix of all? Yes → search [3, 4]
#
#   left=3, right=4, mid=3
#   Is "flo" prefix of all? No ("flight" has "fli") → search [3, 2]
#
#   left=3, right=2 → loop ends
#
#   Return strs[0][:2] = "fl"

Strings: ["flower", "flow", "flight"]
 
Trie structure:
 
        (root)
           │
           f
           │
           l
          / \
         o   i
         │    │
         w    g
        / \    │
       (·)  e   h
             │   │
             r   t
             │   │
            (·) (·)
 
(·) = end of word marker
 
Finding LCP:
1. Start at root
2. 'f' - only one child, continue → LCP so far: "f"
3. 'l' - TWO children ('o' and 'i'), STOP
4. Return "fl"
 
The branching point reveals the LCP!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

class TrieNode:
    """Trie node for LCP computation."""
    __slots__ = ['children', 'is_end', 'count']
    
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end: bool = False  # Marks end of a word
        self.count: int = 0  # Number of words passing through
 
 
class LCPTrie:
    """
    Trie optimized for Longest Common Prefix queries.
    
    Build Time: O(S) where S = sum of all string lengths
    LCP Query Time: O(m) where m = LCP length
    Space: O(S) worst case
    """
    
    def __init__(self):
        self.root = TrieNode()
        self.word_count = 0
    
    def insert(self, word: str) -> None:
        """Insert a word into the trie."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1
        node.is_end = True
        self.word_count += 1
    
    def find_lcp(self) -> str:
        """
        Find the longest common prefix of all inserted words.
        
        Traverse the trie until:
        1. Node has multiple children (divergence point)
        2. Node is end of word (one word is prefix of another)
        3. Node has no children (reached end of all words)
        """
        if self.word_count == 0:
            return ""
        
        lcp = []
        node = self.root
        
        while True:
            # Stop if node marks end of word (shortest word ends here)
            if node.is_end:
                break
            
            # Stop if multiple children (strings diverge)
            if len(node.children) != 1:
                break
            
            # Exactly one child - this character is part of LCP
            char = next(iter(node.children))
            lcp.append(char)
            node = node.children[char]
        
        return ''.join(lcp)
 
 
def longest_common_prefix_trie(strs: list[str]) -> str:
    """
    Find LCP using a trie.
    
    Time: O(S) for building + O(m) for query = O(S)
    Space: O(S) for trie
    
    Best for: Multiple LCP queries after initial build
              Or when trie is already built for other purposes
    """
    if not strs:
        return ""
    
    # Handle empty strings
    if any(s == "" for s in strs):
        return ""
    
    trie = LCPTrie()
    for word in strs:
        trie.insert(word)
    
    return trie.find_lcp()
 
 
# Example usage:
strs = ["flower", "flow", "flight"]
print(longest_common_prefix_trie(strs))  # Output: "fl"
 
# The trie also supports:
# - Adding more strings and recomputing LCP
# - LCP for subsets of strings (with count-based filtering)
# - Prefix existence queries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# Application: Find common directory to simplify paths
def simplify_paths(file_paths: list[str]) -> tuple[str, list[str]]:
    """
    Given file paths, extract common prefix and relative paths.
    
    Example:
        Input: ["/home/user/docs/a.txt", "/home/user/docs/b.txt", "/home/user/docs/sub/c.txt"]
        Output: ("/home/user/docs/", ["a.txt", "b.txt", "sub/c.txt"])
    """
    if not file_paths:
        return "", []
    
    # Split paths into components
    split_paths = [p.split('/') for p in file_paths]
    
    # Find LCP of path components
    lcp_components = []
    min_len = min(len(p) for p in split_paths)
    
    for i in range(min_len):
        component = split_paths[0][i]
        if all(p[i] == component for p in split_paths):
            lcp_components.append(component)
        else:
            break
    
    # Ensure we don't include partial directory names
    common_prefix = '/'.join(lcp_components)
    if common_prefix and not common_prefix.endswith('/'):
        common_prefix += '/'
    
    # Generate relative paths
    relative_paths = [
        p[len(common_prefix):] if p.startswith(common_prefix) else p
        for p in file_paths
    ]
    
    return common_prefix, relative_paths
 
 
# Usage
paths = [
    "/home/user/projects/myapp/src/main.py",
    "/home/user/projects/myapp/src/utils.py",
    "/home/user/projects/myapp/tests/test_main.py"
]
 
common, relative = simplify_paths(paths)
print(f"Common prefix: {common}")
print(f"Relative paths: {relative}")
 
# Output:
# Common prefix: /home/user/projects/myapp/
# Relative paths: ['src/main.py', 'src/utils.py', 'tests/test_main.py']