Strings

Slice vs Array

In Go, the syntax for arrays and slices differs, and the presence or absence of a number within the square brackets ([]) distinguishes them:

Array

• An array has a fixed size, and its size is specified within the square brackets.
  • Example: var arr [5]int
  • This creates an array of 5 integers. The size of the array is fixed and cannot be changed.

Slice

• A slice does not have a size specified in the square brackets, which allows it to be dynamic.
  • Example: var slice []int
    • This creates a slice of integers. Slices are more flexible because they can grow or shrink in size using functions like append.
  • Initialization: make([]int, length, capacity)
    • Example, make([]int, 0, 10)
    • allocates an underlying array of size 10 and returns a slice of length 0 and capacity 10 that is backed by this underlying array.

To summarize:

• Array: [N]T where N is the length (e.g., [5]int)
• Slice: []T where the length is not specified (e.g., []int)

Slices in Go are more commonly used due to their flexibility, while arrays are used when you need a fixed-size collection.

Golang Strings Copy

In Go, copying a string can be done in several ways, each with its own space complexity. Here are the most common methods:

1. Using String Slicing

String slicing is the simplest way to create a copy of a string. In Go, slicing a string creates a new string with the same content.

func copyStringSlice(s string) string {
  return s[:]
}

• Space Complexity: O(n)
  • The space complexity is O(n) because the slice operation creates a new string that occupies the same amount of space as the original string.

2. Using a Loop with String Concatenation

You can manually iterate over each character of the string and concatenate it to a new string. This approach is less efficient in terms of performance but demonstrates manual copying.

func copyStringLoop(s string) string {
    var result string
    for _, ch := range s {
        result += string(ch)
    }
    return result
}

• Space Complexity: O(n)
  • The space complexity is O(n) because each character from the original string is copied into a new string. Additionally, Go strings are immutable, so each concatenation may involve creating a new string.

3. Using fmt.Sprintf

You can use fmt.Sprintf to create a copy of the string. While it’s not specifically designed for copying strings, it effectively creates a new string.

import "fmt"

func copyStringSprintf(s string) string {
    return fmt.Sprintf("%s", s)
}

• Space Complexity: O(n)
  • The space complexity is O(n) because the new string will have the same length as the original.

4. Using strings.Builder

strings.Builder is a more efficient way to build a string if you’re constructing it piece by piece. It can be used to copy a string as well.

	// strings.Builder
	// will help us to convert the byte buffer into string
	// sb.WriteByte is helpful
	// sb.String()

	// Convert result int array to string
	var sb strings.Builder
	for _, num := range result {
		if !(sb.Len() == 0 && num == 0) { // Skip leading zeros
			sb.WriteByte(byte(num + '0'))
		}
	}

	return sb.String()

• Space Complexity: O(n)
  • The space complexity is O(n) because strings.Builder internally allocates space to store the string, and this space is proportional to the length of the input string.

5. Using copy with Byte Slices

You can convert the string to a byte slice, copy it using the copy function, and then convert it back to a string.

func copyStringWithBytes(s string) string {
    b := []byte(s)
    copyB := make([]byte, len(b))
    copy(copyB, b)
    return string(copyB)
}

• Space Complexity: O(n)
  • The space complexity is O(n) because the byte slice requires additional memory, and a new string is created from the copied byte slice.

6. Using append with Byte Slices

This method involves appending the bytes of the string into a new byte slice and converting it back to a string.

func copyStringWithAppend(s string) string {
    b := []byte(s)
    copyB := append([]byte{}, b...)
    return string(copyB)
}

• Space Complexity: O(n)
  • The space complexity is O(n) because append creates a new byte slice, and the final conversion to a string also requires memory proportional to the length of the string.

7. Using strings.Clone (Go 1.18+)

In Go 1.18 and above, strings.Clone can be used to create a distinct copy of a string:

sub := strings.Clone(inputString[start:end])

This method creates a copy of the string’s underlying data, ensuring it’s not shared with the original string.

Summary of Space Complexity

1. String Slicing: O(n)
2. Loop with Concatenation: O(n)
3. fmt.Sprintf: O(n)
4. strings.Builder: O(n)
5. copy with Byte Slices: O(n)
6. append with Byte Slices: O(n)
7. strings.Clone : O(n)

All the methods have a space complexity of O(n), where n is the length of the string. However, they differ in terms of performance and readability, with slicing and using strings.Builder typically being the most efficient and idiomatic approaches in Go.

Common string – int conversion

Q1. Convert a String into an Integer (int and int32)

• Using strconv.Atoi: For converting a string to int

import "strconv"

num, err := strconv.Atoi("123")
if err != nil {
    fmt.Println("Error:", err)
}
fmt.Println("int:", num) // Output: int: 123

• Using strconv.ParseInt: For converting to int32

num, err := strconv.ParseInt("123", 10, 32) // Base 10, bit size 32
if err != nil {
    fmt.Println("Error:", err)
}
fmt.Println("int32:", int32(num)) // Output: int32: 123

Q2. Convert a Char into an Integer (int and int32)

If you have a single character (rune or byte), you can convert it directly:

• Using ASCII manipulation

ch := '7' // Single character
num := ch - '0' // '0' has an ASCII value of 48
fmt.Println("int:", num) // Output: int: 7

For int32: Same process

num := int32(ch - '0')
fmt.Println("int32:", num) // Output: int32: 7

Q3. Convert an Integer (int and int32) into a String

Using strconv.Itoa: For int

import "strconv"

str := strconv.Itoa(123)
fmt.Println("string:", str) // Output: string: "123"

Using fmt.Sprintf: For both int and int32

str := fmt.Sprintf("%d", int32(123))
fmt.Println("string:", str) // Output: string: "123"

Q4. Convert an Integer (int and int32) into a Char

Using ASCII manipulation

num := 7
ch := rune(num + '0') // Add '0' to convert to a character
fmt.Printf("char: %c\n", ch) // Output: char: 7

For int32: Same logic applies

var num int32 = 7
ch := rune(num + '0')
fmt.Printf("char: %c\n", ch) // Output: char: 7

Common String Operations in LeetCode

1. String Reversal

str := "hello"
reversed := ""
for _, ch := range str {
    reversed = string(ch) + reversed
}
fmt.Println("Reversed:", reversed) // Output: "olleh"

2. Substring Extraction

str := "leetcode"
fmt.Println("Substring:", str[1:4]) // Output: "eet"

3. Splitting Strings

import "strings"

str := "1,2,3"
parts := strings.Split(str, ",")
fmt.Println("Parts:", parts) // Output: ["1", "2", "3"]

4. Joining Strings

joined := strings.Join([]string{"a", "b", "c"}, ",")
fmt.Println("Joined:", joined) // Output: "a,b,c"

5. Character Count/Frequency

freq := make(map[rune]int)
str := "leetcode"
for _, ch := range str {
    freq[ch]++
}
fmt.Println("Frequency:", freq) // Output: map[e:3 l:1 t:1 c:1 o:1 d:1]

6. String Comparison

if "abc" == "abc" {
    fmt.Println("Strings are equal")
}

7.String Contains

import "strings"

fmt.Println(strings.Contains("leetcode", "leet")) // Output: true

8. String Indexing

fmt.Println(strings.Index("leetcode", "code")) // Output: 4

9.String Conversion to Bytes and Back

b := []byte("abc")
str := string(b)
fmt.Println("Bytes:", b, "String:", str) // Output: Bytes: [97 98 99] String: abc

10.Palindrome Check

str := "madam"
isPalindrome := true
for i := 0; i < len(str)/2; i++ {
    if str[i] != str[len(str)-1-i] {
        isPalindrome = false
        break
    }
}
fmt.Println("Is Palindrome:", isPalindrome) // Output: true

KMP Algorithm for Pattern Searching

• Knuth–Morris–Pratt algorithm