Implementing Core String Functions in Go

This challenge asks you to reimplement a subset of the functionality found in Go's standard strings package. The goal is to understand the underlying algorithms and data manipulation techniques used for common string operations. Successfully completing this challenge will solidify your understanding of string handling in Go and improve your problem-solving skills.

Problem Description

You are tasked with creating a simplified version of the strings package, focusing on three key functions: Contains, Count, and Replace. Your implementation should accurately replicate the behavior of these functions as defined in the standard library.

What needs to be achieved:

• Contains(s, substr string) bool: This function should determine if the substring substr exists within the string s. It should return true if substr is found, and false otherwise. The search should be case-sensitive.
• Count(s, substr string) int: This function should count the number of non-overlapping occurrences of the substring substr within the string s.
• Replace(s, old, new string) string: This function should replace all non-overlapping occurrences of the substring old within the string s with the substring new.

Key Requirements:

• Your implementation must be efficient and avoid unnecessary memory allocations.
• The functions should handle empty strings and substrings gracefully.
• The Replace function should return a new string with the replacements made, leaving the original string unchanged.
• The Count function should return 0 if either s or substr is empty.

Expected Behavior:

The functions should behave identically to their counterparts in the standard strings package, with the exception of any performance optimizations you might implement.

Edge Cases to Consider:

• Empty input strings (s or substr are empty).
• substr is longer than s.
• old is empty in the Replace function (should not result in infinite loops or unexpected behavior).
• Overlapping occurrences of substr in Count. (e.g., s = "abababa", substr = "aba")
• old is not found in Replace.

Examples

Example 1:

Input: s = "hello world", substr = "world"
Output: true
Explanation: The substring "world" is present in "hello world".

Example 2:

Input: s = "hello world", substr = "go"
Output: false
Explanation: The substring "go" is not present in "hello world".

Example 3:

Input: s = "abababa", substr = "aba"
Output: 2
Explanation: The substring "aba" appears twice in "abababa" (non-overlapping).

Example 4:

Input: s = "hello world", old = "world", new = "universe"
Output: "hello universe"
Explanation: "world" is replaced with "universe".

Example 5:

Input: s = "hello world", old = "go", new = "universe"
Output: "hello world"
Explanation: "go" is not found, so the string remains unchanged.

Example 6:

Input: s = "aaaa", old = "", new = "b"
Output: "aaaa"
Explanation: Replacing an empty string with another string should not modify the original string.

Constraints

• The maximum length of the input strings s, substr, old, and new will be 1000 characters.
• The functions should execute within a reasonable time limit (e.g., less than 1 second for typical inputs).
• Memory usage should be minimized.

Notes

• Consider using string slicing and iteration to implement the functions.
• Pay close attention to edge cases and boundary conditions.
• While performance is a consideration, correctness is paramount. Focus on producing a correct implementation first, then optimize if necessary.
• You do not need to implement the entire strings package, only the Contains, Count, and Replace functions.
• Think about how to avoid unnecessary string allocations, especially in the Replace function. Pre-allocating memory can improve performance.