Introduction to String Manipulation in Go

Welcome back! This lesson will focus on advanced string manipulation in Go. String manipulation is a vital skill for solving real-world programming challenges. Gaining proficiency in these techniques will enable you to decompose complex problems into simpler ones and improve your adaptability when working within different programming languages or contexts.

Let's explore a common coding interview challenge: finding the longest common starting sequence of characters (prefix) shared among a slice of strings. Given a slice of strings such as {"flower", "flow", "flight"}, the longest common prefix is "fl".

Our strategy for solving this problem in Go is:

1. Check for Empty Input: If the input slice is empty, the function will return an empty string as there's nothing to compare.
2. Identify the Shortest String: To optimize the comparison, find the shortest string, which limits the number of comparisons needed in subsequent steps.
3. Character by Character Comparison: Compare characters of the shortest string with corresponding characters in all other strings.
   • For each character index, store the character for reference.
   • Traverse all strings in the slice to check for character matches at each index. If any mismatch is detected, return the substring from the start up to (but excluding) that index.
4. Return the Shortest String: If no mismatch occurs, the function returns the shortest string as the longest common prefix.

For example, given the input {"flower", "flow", "flight"}:

1. The slice is not empty.
2. The function identifies "flow" as the shortest.
3. Start comparing each character of "flow" with the others:
   • At index 0, all strings have 'f'.
   • At index 1, all strings have 'l'.
   • At index 2, "flower" and "flow" have 'o', but "flight" has 'i', leading to a mismatch.
4. A mismatch at index 2 results in returning the substring "fl".

Here's how to implement this algorithm in Go:

package main

import (
    "fmt"
)

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    
    shortest := strs[0]
    for _, str := range strs {
        if len(str) < len(shortest) {
            shortest = str
        }
    }

    for i := 0; i < len(shortest); i++ {
        charToCheck := shortest[i]
        for _, str := range strs {
            if i >= len(str) || str[i] != charToCheck {
                return shortest[:i]
            }
        }
    }
    return shortest
}

func main() {
    strs := []string{"flower", "flow", "flight"}
    fmt.Println(longestCommonPrefix(strs)) // Outputs: "fl"
}