A Collection of Essential string algorithms and questions in Golang

strings.go

package main

import (
	"fmt"
	"strings"
	"unicode"
)

// 1. Longest Common Prefix
func longestCommonPrefix(strs []string) {
	if len(strs) == 0 {
		fmt.Println("")
		return
	}
	prefix := strs[0]
	for _, word := range strs[1:] {
		for !strings.HasPrefix(word, prefix) {
			prefix = prefix[:len(prefix)-1]
			if prefix == "" {
				fmt.Println("")
				return
			}
		}
	}
	fmt.Println(prefix)
}

// 2. Fizz Buzz
func fizzBuzz(n int) {
	for i := 1; i <= n; i++ {
		if i%3 == 0 && i%5 == 0 {
			fmt.Println("FizzBuzz")
		} else if i%3 == 0 {
			fmt.Println("Fizz")
		} else if i%5 == 0 {
			fmt.Println("Buzz")
		} else {
			fmt.Println(i)
		}
	}
}

// 3. Longest Repeating Character Replacement
func characterReplacement(s string, k int) {
	count := make([]int, 26)
	left := 0
	maxCount := 0
	result := 0

	for right := 0; right < len(s); right++ {
		count[s[right]-'A']++
		maxCount = max(maxCount, count[s[right]-'A'])

		if (right - left + 1 - maxCount) > k {
			count[s[left]-'A']--
			left++
		}
		result = max(result, right-left+1)
	}
	fmt.Println(result)
}

// 4. Longest Substring Without Repeating Characters
func lengthOfLongestSubstring(s string) {
	seen := make(map[byte]int)
	left := 0
	maxLen := 0

	for right := 0; right < len(s); right++ {
		if idx, ok := seen[s[right]]; ok && idx >= left {
			left = idx + 1
		}
		seen[s[right]] = right
		maxLen = max(maxLen, right-left+1)
	}
	fmt.Println(maxLen)
}

// 5. Minimum Window Substring
func minWindow(s string, t string) {
	if len(t) > len(s) {
		fmt.Println("")
		return
	}

	tCount := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		tCount[t[i]]++
	}

	start, minLen := 0, len(s)+1
	formed := 0
	required := len(tCount)
	window := make(map[byte]int)

	left := 0
	for right := 0; right < len(s); right++ {
		ch := s[right]
		window[ch]++
		if tCount[ch] > 0 && window[ch] == tCount[ch] {
			formed++
		}

		for formed == required {
			if (right - left + 1) < minLen {
				start = left
				minLen = right - left + 1
			}
			window[s[left]]--
			if tCount[s[left]] > 0 && window[s[left]] < tCount[s[left]] {
				formed--
			}
			left++
		}
	}

	if minLen == len(s)+1 {
		fmt.Println("")
	} else {
		fmt.Println(s[start : start+minLen])
	}
}

// 6. Valid Anagram
func isAnagram(s, t string) {
	if len(s) != len(t) {
		fmt.Println(false)
		return
	}
	count := make(map[rune]int)
	for _, ch := range s {
		count[ch]++
	}
	for _, ch := range t {
		count[ch]--
		if count[ch] < 0 {
			fmt.Println(false)
			return
		}
	}
	fmt.Println(true)
}

// 7. Group Anagrams
func groupAnagrams(strs []string) {
	anagrams := make(map[[26]int][]string)
	for _, word := range strs {
		var count [26]int
		for _, c := range word {
			count[c-'a']++
		}
		anagrams[count] = append(anagrams[count], word)
	}
	for _, group := range anagrams {
		fmt.Println(group)
	}
}

// 8. Valid Parentheses
func isValidParentheses(s string) {
	stack := []rune{}
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	for _, c := range s {
		if c == '(' || c == '{' || c == '[' {
			stack = append(stack, c)
		} else {
			if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
				fmt.Println(false)
				return
			}
			stack = stack[:len(stack)-1]
		}
	}
	fmt.Println(len(stack) == 0)
}

// 9. Valid Palindrome
func isPalindrome(s string) {
	s = strings.ToLower(s)
	filtered := ""
	for _, c := range s {
		if unicode.IsLetter(c) || unicode.IsDigit(c) {
			filtered += string(c)
		}
	}
	l, r := 0, len(filtered)-1
	for l < r {
		if filtered[l] != filtered[r] {
			fmt.Println(false)
			return
		}
		l++
		r--
	}
	fmt.Println(true)
}

// 10. Longest Palindromic Substring
func longestPalindrome(s string) {
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		l1, r1 := expandAroundCenter(s, i, i)
		l2, r2 := expandAroundCenter(s, i, i+1)
		if r1-l1 > end-start {
			start, end = l1, r1
		}
		if r2-l2 > end-start {
			start, end = l2, r2
		}
	}
	fmt.Println(s[start : end+1])
}

func expandAroundCenter(s string, left, right int) (int, int) {
	for left >= 0 && right < len(s) && s[left] == s[right] {
		left--
		right++
	}
	return left + 1, right - 1
}

// 11. Palindromic Substrings
func countSubstrings(s string) {
	count := 0
	for i := 0; i < len(s); i++ {
		count += expandAndCount(s, i, i)
		count += expandAndCount(s, i, i+1)
	}
	fmt.Println(count)
}

func expandAndCount(s string, left, right int) int {
	count := 0
	for left >= 0 && right < len(s) && s[left] == s[right] {
		count++
		left--
		right++
	}
	return count
}

// 12. Palindrome Linked List (Just logic simulation with slice)
func isPalindromeList(values []int) {
	l, r := 0, len(values)-1
	for l < r {
		if values[l] != values[r] {
			fmt.Println(false)
			return
		}
		l++
		r--
	}
	fmt.Println(true)
}

// Utility
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Main to test
func main() {
	longestCommonPrefix([]string{"flower", "flow", "flight"})
	fizzBuzz(15)
	characterReplacement("AABABBA", 1)
	lengthOfLongestSubstring("abcabcbb")
	minWindow("ADOBECODEBANC", "ABC")
	isAnagram("anagram", "nagaram")
	groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"})
	isValidParentheses("()[]{}")
	isPalindrome("A man, a plan, a canal: Panama")
	longestPalindrome("babad")
	countSubstrings("abc")
	isPalindromeList([]int{1, 2, 2, 1})
}