String Concatenation

String Concatenation

String Concatenation is the fundamental operation of joining two or more strings end-to-end to form a single, contiguous string. For example, concatenating "Hello" and "World" results in "HelloWorld".

Implementation Mechanics

• In Static/Low-level Languages (like C): Since strings are fixed-size, null-terminated character arrays, you must ensure the destination array has sufficient capacity to hold both strings. The algorithm scans to find the null terminator ('\0') of the first string, overwrites it with the first character of the second string, and copies all subsequent characters sequentially, ensuring a new null terminator is appended at the very end.
• In Dynamic/High-level Languages (like C++): Objects like std::string overload the + or += operators, dynamically reallocating memory and appending the characters under the hood.
• In Immutable String Environments (like Java/Python/JavaScript): Because strings are immutable, concatenation doesn't modify the existing strings. Instead, the runtime allocates an entirely new memory block large enough to fit both sequences, copies both strings into it, and returns a new string reference.

Complexity Analysis

• Time Complexity:
  • Best Case: O(M) (where M is the length of the second string, if the starting address of the null-terminator is already known)
  • Average Case: O(N + M) (where N and M are the lengths of the two strings, since we must scan the first string to locate its end, and copy all M characters of the second string)
  • Worst Case: O(N + M)
• Space Complexity: O(N + M) (since we need space in memory to store the combined characters)