Arrays and Strings

Arrays and strings are the most foundational concepts in programming. They are the basic building blocks for solving complex problems. They both have a core similarity—and one critical difference—that confuses nearly everyone. Mastering this distinction is the real "superpower" in algorithmic problem solving.

In simple terms, both arrays (1D) and strings are very similar in nature and represent "contiguous ordered collection of elements" which means elements are stored right next to each other in the memory. Because these elements are stored right next to each other in memory, the computer can find any element instantly.

This kind of accessing elements instantly is called constant time access, or O(1). This isn't magic; it's simple math. To explain this in simple terms, the computer knows the start address in memory and the size of each element (this varies based on the computer architecture and programming language), so it can calculate the exact location of index [5] or index [5,000,000] with simple one step multiplication and addition.

Here is the formula that languages use to access the elements of arrays and strings with constant time.

The word "array" can mean different things in different languages. In Python, the default list is actually a dynamic array. It can grow and shrink automatically. In C++ or Java, a basic int[] array has a fixed size that cannot be changed. You must use a Vector or ArrayList to get a dynamic array.

From this point on, this series of articles will match what you see in algorithm problems: when we say "array," we will always mean a "dynamic array."

Similarly, strings are almost arrays with a hidden trap that depends on your language. In Python and Java, strings are immutable (they cannot be changed). In C++, std::string is mutable (it can be changed, just like an array).

This one difference—mutability vs. immutability—is the main reason why strings and arrays are treated as two separate, special data types. This simple concept of immutability can drastically affect algorithm performance; for example, modifying a single character can change an operation from O(1) to O(n). Why so? Why do we need to care so much about mutability and immutability?

Imagine you have an array greetings = ['h', 'e', 'l', 'l', 'o'], which is mutable, and a string greetings = "hello", which is immutable. Modifying a single character in the array—for example, changing the lowercase 'h' to an uppercase 'H'—takes O(1) time.

This is because the array stores its elements in individual memory locations, so you can directly access and change one element without touching the rest. In contrast, strings cannot be changed once they are created.

So, when you try to modify a single character in a string (in any form, either by concatenating or by updating characters at a specific index), the program has to create a new string and copy all the existing characters into it, including your small change. This copying process takes O(n) time since every character in the original string must be duplicated. In theory, you have to go through each character in the string and copy it and then make that tiny change you wanted. Now, imagine a string with a length of 100,000,000—you want to add just one more character, and all 100,000,000 characters need to be copied to a new string with the additional character added at the end. Have you thought about how expensive rebuilding a string is?

So far, you've learned everything you need to know about arrays and strings. But have you considered this simple question: how can we deal with immutability in strings and avoid rebuilding the entire string for every single or multi-character update? You might be thinking about how convenient arrays are, right? solution to your immutability problem. How can we make string operations more efficient? Are there data structures designed to help us update large text data without rebuilding everything each time?

Usually, apart from languages like C++, many programming languages provide special mechanisms to handle what's often called the "O(n) string building" problem caused by immutability.

Usually, apart from languages like C++, many programming languages provide special mechanisms to handle what's often called the "O(n) string building" problem caused by immutability. It's not that these languages use O(n) string building to solve immutability—instead, they introduce mutable alternatives, such as StringBuilder in Java or StringBuffer in JavaScript, to achieve O(1) or amortized efficient concatenation.

The reason we are focusing our time on understanding immutability is because, as mentioned earlier, modifying a single character in a string can take O(n) time. Now imagine having to make multiple changes across the entire string—this can lead to an overall time complexity of O(n²). In most algorithmic problems, the input is often a string or an array, so learning how to efficiently manipulate these data types can greatly boost your confidence and problem-solving ability.

So, it's your responsibility to search for a better way to build strings in your language of choice. But in Python, here is how you can do it in O(n) time:

• Declare a list
• When building the string, add characters to the list. Each append operation takes O(1) time. Across n operations, it will cost O(n) in total.
• Once finished, convert the list to a string using "".join(arr)

def build_string(s):
    arr = []              # Declare an empty list
    for c in s:           # Append each character to the list
        arr.append(c)     # O(1) per append
 
    return "".join(arr)   # Join all characters into a string, O(n)

Before moving on to our first pattern for solving problems related to arrays and strings, I want you to review the time complexity comparison table below. This comparison assumes that strings are immutable.