15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Immutable strings cannot change after creation, so every edit builds a new string and the old one stays as it was. A mutable character array lets you assign into one existing cell. Replacing one character costs O(1) in an array and O(n) in an immutable string, because the new string holds all n characters.
| Character array write | O(1) time, O(1) auxiliary space, changes the array |
|---|---|
| Immutable string replace | O(n) time, O(n) result storage, original unchanged |
| Valid index | 0 <= i < n; index n is not a position |
| Rebinding | s = result points the name at the new string, the old string is untouched |
| Pick an array when | you need many in-place character edits |
A text value can be represented in two ways:
Check the representation before deciding what an assignment means.
If a is a character array, this can change its existing storage:
1a[1] ← 'a'If s is an immutable string, this is not an in-place write. A replacement operation produces another string value. A variable may then be rebound to refer to that result.
1result ← replaceAt(s, 1, 'a')
2s ← resultThe rebinding changes what s denotes. It does not modify the old immutable string.
For repeated character edits that require in-place changes, use a mutable character array. When the original text must remain available, use immutable-string behavior and return a newly formed result.
Use the same text in both representations.
Replace index
1with'a'in"cat".
Start at index 0.
| Index | 0 | 1 | 2 |
|---|---|---|---|
Characters in "cat" | c | a | t |
The target index is 1. It is valid because:
10 ≤ 1 < 3Now show the two forms of the data.
1immutable string s = "cat"
2
3character array a:
4index: 0 1 2
5value: [c] [a] [t]The replacement character is already 'a'. The visible characters remain c, a, t. The representations have different semantics:
A character array can be written in place at index 1. An immutable string cannot be written: replacing a character builds a separate result, and s is rebound to it. Here both end as "cat".
Both representations display the same characters. Their allowed operations differ.
Assign 'a' at index 1.
1a[1] ← 'a'The array becomes:
1index: 0 1 2
2value: [c] [a] [t]Only index 1 was the target of the assignment. Since it already contained 'a', the displayed array is unchanged. The operation still writes in place to an existing cell.
Now replace index 1 of s with 'a'.
1result ← replacement of s at index 1 with 'a'The operation constructs:
1old string: s = "cat"
2result: "cat"The old value remains unchanged. The result equals "cat" because index 1 already held 'a'.
If the caller wants s to denote the result, it performs a rebinding:
1s ← resultNow:
1s = "cat"The visible value is still "cat". No in-place write occurred to the old immutable string. The variable name now denotes the newly constructed result.
For an in-place character-array edit:
For the example, index 1 is the target. Positions 0 and 2 remain c and t.
For an immutable-string replacement:
The invariant for the array operation is:
During an in-place character-array edit, every array position other than the assigned target retains its prior value.
For the immutable operation:
During an immutable-string operation, the original string value remains unchanged.
When constructing the result one position at a time, use this loop invariant:
Before copying position
p, the result already contains the correct replacement output for every position from0throughp - 1, and the input string has not changed.
First validate the target index. A replacement is valid only when:
10 ≤ i < lengthIndex length is not a valid existing position. It describes a location after the final character.
Once the index is valid, only one write is needed:
ch to array[i].The supplied array changes.
An immutable string cannot receive that one write. Build a result of the same length:
i.0 through length - 1.i, put ch into the result.The input string is never modified.
Inputs
array: a mutable character arrayi: target indexch: replacement characterMutation behavior
i is valid, the procedure changes array[i].Return value
InvalidIndex if i is out of range.1PROCEDURE replaceInArray(array, i, ch)
21. n ← length(array)
32. IF i < 0 OR i ≥ n
43. RETURN InvalidIndex
54. END IF
65. array[i] ← ch
76. RETURN array
8END PROCEDUREInputs
text: an immutable stringi: target indexch: replacement characterMutation behavior
text.Return value
i replaced.InvalidIndex if i is out of range.Helper contract
makeString(resultChars) accepts a character sequence and returns a string with exactly those characters in the same order. It does not change text.1FUNCTION replaceAt(text, i, ch)
21. n ← length(text)
32. IF i < 0 OR i ≥ n
43. RETURN InvalidIndex
54. END IF
65. resultChars ← new character array of length n
76. p ← 0
87. WHILE p < n
98. IF p = i
109. resultChars[p] ← ch
1110. ELSE
1211. resultChars[p] ← text[p]
1312. END IF
1413. p ← p + 1
1514. END WHILE
1615. RETURN makeString(resultChars)
17END FUNCTIONValid indices run from 0 to n - 1.
Use the board example:
1text = "cat"
2i = 1
3ch = 'a'The input array is:
1array:
2index: 0 1 2
3value: [c] [a] [t]| Line | Action | Array state |
|---|---|---|
| 1 | n ← length(array) gives n = 3 | [c, a, t] |
| 2–4 | Check 1 < 0 OR 1 ≥ 3. Both are false. | [c, a, t] |
| 5 | Assign array[1] ← 'a' | [c, a, t] |
| 6 | Return array | [c, a, t] |
The target cell was written. Indices 0 and 2 were not assigned.
| Line | Action | text | resultChars |
|---|---|---|---|
| 1 | n ← length(text) gives n = 3 | "cat" | not created |
| 2–4 | Check 1 < 0 OR 1 ≥ 3. Both are false. | "cat" | not created |
| 5 | Create length-3 result array. | "cat" | [_, _, _] |
| 6 | Set p ← 0. | "cat" | [_, _, _] |
Now follow every loop pass.
| Line | p | Action | text | resultChars after the pass |
|---|---|---|---|---|
| 7 | 0 | 0 < 3, enter loop | "cat" | [_, _, _] |
| 8 | 0 | 0 = 1 is false | "cat" | [_, _, _] |
| 11 | 0 | Copy text[0], which is c | "cat" | [c, _, _] |
| 13 | 0 | Set p ← 1 | "cat" | [c, _, _] |
| 7 | 1 | 1 < 3, enter loop | "cat" | [c, _, _] |
| 8 | 1 | 1 = 1 is true | "cat" | [c, _, _] |
| 9 | 1 | Write replacement a | "cat" | [c, a, _] |
| 13 | 1 | Set p ← 2 | "cat" | [c, a, _] |
| 7 | 2 | 2 < 3, enter loop | "cat" | [c, a, _] |
| 8 | 2 | 2 = 1 is false | "cat" | [c, a, _] |
| 11 | 2 | Copy text[2], which is t | "cat" | [c, a, t] |
| 13 | 2 | Set p ← 3 | "cat" | [c, a, t] |
| 7 | 3 | 3 < 3 is false, leave loop | "cat" | [c, a, t] |
| 15 | — | makeString(resultChars) returns "cat" | "cat" | [c, a, t] |
The returned value is "cat". The supplied input text remains "cat" throughout the trace.
Assume the target index is valid.
Initialization. Before line 5, no array position has changed. Every position has its original value.
Preservation. Line 5 assigns only array[i]. No assignment targets any other index. Every position other than i retains its prior value.
Termination. The procedure performs the one assignment and returns. The target position contains ch, and all non-target positions retain their old values.
If the index is invalid, lines 2–4 return InvalidIndex before any assignment. The procedure does not attempt an out-of-range write.
Assume the target index is valid.
Initialization. Before the loop, resultChars has length n and no input character has changed. Before position 0, there are no earlier result positions to prove correct, so the loop invariant holds.
Preservation. Suppose the result positions 0 through p - 1 are correct before a loop pass.
p = i, line 9 writes ch, which is the required replacement character.text[p], which is the required original character for that position.The function writes only to resultChars, never to text. After line 13 increments p, all positions before the new p are correct, and the original string remains unchanged.
Termination. The loop ends when p = n. Every result position from 0 through n - 1 is correct: position i contains ch, and every other position contains the corresponding input character. Line 15 converts that full sequence into the returned string. Since no line writes to text, the original input remains unchanged.
If the index is invalid, the function returns at lines 2–4 before allocating or writing a result position.
After validation, the procedure performs one indexed assignment:
1array[i] ← chThat updates one existing cell.
O(1)O(1)The bounds check is also constant work.
Let n be the string length.
The function creates n result positions. The loop runs once for each p from 0 through n - 1.
For each pass, it performs one comparison with i and writes one character into resultChars. The function produces n output characters.
O(n)O(n) for the newly constructed stringO(1) for n, p, i, and chWhen a convention counts returned output storage as space, report O(n) space. When it separates output storage from auxiliary space, report O(1) auxiliary space and O(n) result storage.
For "cat", the immutable algorithm performs three loop passes because the input length is 3.
Incorrect assumption:
1s[0] ← 'B'Small input that exposes it:
1s = "bat"Wrong claim:
1s becomes "Bat" in placeWhy it fails: immutable-string behavior does not permit a write into an existing string character.
Correction: construct a separate result, "Bat", and either return it or rebind s to it.
1result ← replaceAt(s, 0, 'B')
2s ← resultThe old string value was not mutated.
Incorrect outline:
1chars ← character array copied from text
2chars[i] ← ch
3RETURN textSmall input that exposes it:
1text = "cat"
2i = 0
3ch = 'b'Wrong output:
1"cat"The edited representation contains [b, a, t], but returning text discards that work.
Correction: return the edited representation when that is the required result, or convert it into the required string result and return that value.
1RETURN makeString(chars)length as appendIncorrect condition:
1IF i ≤ length(array)Small input that exposes it:
1array = [c, a, t]
2i = 3
3ch = xWrong result claim:
1[c, a, t, x]Index 3 lies after the final cell and is invalid for indexed replacement. Valid replacement indices for a length-3 array are 0, 1, and 2.
Correction:
1IF i < 0 OR i ≥ length(array)
2 RETURN InvalidIndex| Input | Operation | Required outcome |
|---|---|---|
array = [], i = 0, ch = x | Array replacement | InvalidIndex |
array = [x], i = 0, ch = y | Array replacement | Array becomes [y] |
text = "cat", i = 1, ch = a | Immutable replacement | Return "cat"; original text remains unchanged |
Any length-3 sequence, i = -1 | Replacement | InvalidIndex |
Any length-3 sequence, i = 3 | Replacement | InvalidIndex |
Implement:
1replaceAt(text, i, ch)Contract to satisfy:
i replaced by ch.1INVALID_INDEX = "INVALID_INDEX"
2
3def replace_in_array(array, i, ch):
4 n = len(array)
5 if i < 0 or i >= n:
6 return False
7 array[i] = ch # one in-place write
8 return True
9
10def replace_at(text, i, ch):
11 n = len(text)
12 if i < 0 or i >= n:
13 return INVALID_INDEX
14 result_chars = [""] * n # new array; text is never written
15 for p in range(n):
16 result_chars[p] = ch if p == i else text[p]
17 return "".join(result_chars)
18
19print(replace_at("cat", 1, "a"))
20s = "bat"
21print(replace_at(s, 0, "B"))
22print("original: " + s)
23array = list("bat")
24replace_in_array(array, 0, "B")
25print("array: " + "".join(array))
26print(replace_at(s, 3, "x"))1public class Main {
2 static final String INVALID_INDEX = "INVALID_INDEX";
3
4 static boolean replaceInArray(char[] array, int i, char ch) {
5 int n = array.length;
6 if (i < 0 || i >= n) return false;
7 array[i] = ch; // one in-place write
8 return true;
9 }
10
11 static String replaceAt(String text, int i, char ch) {
12 int n = text.length();
13 if (i < 0 || i >= n) return INVALID_INDEX;
14 char[] resultChars = new char[n]; // new array; text is never written
15 for (int p = 0; p < n; p++) {
16 resultChars[p] = (p == i) ? ch : text.charAt(p);
17 }
18 return new String(resultChars);
19 }
20
21 public static void main(String[] args) {
22 System.out.println(replaceAt("cat", 1, 'a'));
23 String s = "bat";
24 System.out.println(replaceAt(s, 0, 'B'));
25 System.out.println("original: " + s);
26 char[] array = "bat".toCharArray();
27 replaceInArray(array, 0, 'B');
28 System.out.println("array: " + new String(array));
29 System.out.println(replaceAt(s, 3, 'x'));
30 }
31}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6bool replaceInArray(vector<char>& array, int i, char ch) {
7 int n = (int)array.size();
8 if (i < 0 || i >= n) return false;
9 array[i] = ch; // one in-place write
10 return true;
11}
12
13// std::string is mutable, so this function treats text as read-only on purpose.
14string replaceAt(const string& text, int i, char ch) {
15 int n = (int)text.size();
16 if (i < 0 || i >= n) return "INVALID_INDEX";
17 vector<char> resultChars(n); // new array; text is never written
18 for (int p = 0; p < n; p++) {
19 resultChars[p] = (p == i) ? ch : text[p];
20 }
21 return string(resultChars.begin(), resultChars.end());
22}
23
24int main() {
25 cout << replaceAt("cat", 1, 'a') << endl;
26 string s = "bat";
27 cout << replaceAt(s, 0, 'B') << endl;
28 cout << "original: " << s << endl;
29 vector<char> array = {'b', 'a', 't'};
30 replaceInArray(array, 0, 'B');
31 cout << "array: " << string(array.begin(), array.end()) << endl;
32 cout << replaceAt(s, 3, 'x') << endl;
33}1const INVALID_INDEX = 'INVALID_INDEX';
2
3function replaceInArray(array, i, ch) {
4 const n = array.length;
5 if (i < 0 || i >= n) return false;
6 array[i] = ch; // one in-place write
7 return true;
8}
9
10function replaceAt(text, i, ch) {
11 const n = text.length;
12 if (i < 0 || i >= n) return INVALID_INDEX;
13 const resultChars = new Array(n); // new array; text is never written
14 for (let p = 0; p < n; p++) {
15 resultChars[p] = p === i ? ch : text[p];
16 }
17 return resultChars.join('');
18}
19
20console.log(replaceAt('cat', 1, 'a'));
21const s = 'bat';
22console.log(replaceAt(s, 0, 'B'));
23console.log('original: ' + s);
24const array = [...'bat'];
25replaceInArray(array, 0, 'B');
26console.log('array: ' + array.join(''));
27console.log(replaceAt(s, 3, 'x'));Because sharing a string is then safe. One value can be reused from the string pool, its hash code can be cached, threads can read it without locks, and a path or class name cannot change after it was checked.
Yes. std::string allows s[i] = 'x' and changes the same object. Python, Java, JavaScript and C# strings do not allow that write, so check the language before you plan an in-place edit.
No. It builds a new string and rebinds the name s to it. The old string value is unchanged. Done in a loop, it can copy the old text on every pass.
A character array has indexed cells you can overwrite, so a write is O(1). An immutable string fixes its characters at creation, so a replacement returns a new string in O(n) time.
It is invalid. For a length-3 sequence the valid indexes are 0, 1 and 2. Index 3 is after the last cell, so replaceAt returns InvalidIndex instead of appending.