15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A string data structure stores an ordered, finite sequence of characters, each at a zero-based index. Reading text[i] is valid only when 0 <= i < n, where n is the length, and it takes O(1) time. Visiting every character is O(n) time and O(1) extra space.
| First index | 0, the last valid index is n - 1 |
|---|---|
| Valid read | 0 <= i < n; index n is not a character |
| Read one character | O(1) time, O(1) auxiliary space |
| Visit every character | O(n) time, O(1) auxiliary space |
| Empty string | Length 0, no valid index |
No prerequisites.
A string is an ordered, finite sequence of characters. “Ordered” means position matters: the first character is different from the second character, even if the characters look similar.
For this course, treat each displayed character as one indexed element unless a later lesson says otherwise. The course uses this algorithm model to trace strings.
A character position can differ from a byte position in a particular programming language or encoding. Keep those ideas separate:
i?”We will use zero-based indexing. The first character has index 0.
Write this string:
1text = "DOG"Its characters appear from left to right in this order:
1D, O, GThere are three characters, so its length is:
1n = 3Start indexing at 0, not 1:
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Character | D | O | G |
The last valid index is one less than the length:
1n - 1 = 3 - 1 = 2So the valid indexes for "DOG" are 0, 1, and 2.
A string read does not change the string. The operation checks an index, then reads the character stored at that position.
1text = "DOG"
2n = 3The string has three indexed character positions.
1index: 0 1 2
2text: D O GEach displayed character receives exactly one index. The indexes increase as we move left to right.
We request:
1text[1]Index 1 is valid because:
10 <= 1 < 3The character at index 1 is:
1OSo:
1text[1] returns OThe string remains unchanged:
1text = "DOG"Now request:
1text[3]Check the boundary:
10 <= 3 < 3The right-hand comparison is false:
13 < 3Therefore index 3 is invalid. It is just after the final character, whose index is 2.
Before reading any character, we must know the string length n.
For a string of length n, an indexed character access is valid only when:
10 <= i < nIn ordinary language:
i cannot be negative.i must be smaller than the length.i = n is not a character position.The invariant for string access is:
For a string of length
n, every indexed character access must use an indexisatisfying0 <= i < n.
For "DOG", where n = 3, the valid indexes are exactly:
10, 1, 2Neither -1 nor 3 names a character in the lesson model.
We need an operation with two inputs:
text, a stringi, a requested indexThe operation must either return the character at i or return the specified invalid-index result.
Start by finding the length:
1n = length(text)Then test the invariant’s boundary condition:
10 <= i < nThere are two cases:
text[i] is a valid indexed read.The read does not mutate text. It only returns one character.
Inputs:
text: a string treated as an ordered sequence of displayed charactersi: an integer indexReturn value:
text[i] when i is validINVALID_INDEX otherwiseMutation behavior:
text.Helper contract:
length(text) returns the number of indexed characters in the course’s character-level model.11 function characterAt(text, i):
22 n <- length(text)
33
44 if i < 0 or i >= n:
55 return INVALID_INDEX
66
77 return text[i]Line 4 rejects both invalid boundary directions:
i < 0 rejects negative indexes.i >= n rejects i = n and indexes beyond the end.Use the board example and request index 1:
1text = "DOG"
2i = 1characterAt("DOG", 1)| Pseudocode line | State or action |
|---|---|
| 1 | Call characterAt(text, i) with text = "DOG" and i = 1. |
| 2 | Set n <- length("DOG"). Now n = 3. |
| 4 | Test i < 0 or i >= n. Substitute values: 1 < 0 or 1 >= 3. Both comparisons are false. |
| 5 | Skip this line because the condition on line 4 is false. |
| 7 | Return text[1], which is O. |
Result:
1OThe input string was not changed:
1text = "DOG"characterAt("DOG", 3)Now use the same string with the requested index from State 3:
1text = "DOG"
2i = 3| Pseudocode line | State or action |
|---|---|
| 1 | Call characterAt(text, i) with text = "DOG" and i = 3. |
| 2 | Set n <- length("DOG"). Now n = 3. |
| 4 | Test i < 0 or i >= n. Substitute values: 3 < 0 or 3 >= 3. The second comparison is true. |
| 5 | Return INVALID_INDEX. |
| 7 | This line is not reached. |
Result:
1INVALID_INDEXNo attempt is made to read text[3].
We show that characterAt(text, i) returns the character at i exactly when i is a valid index, and otherwise returns INVALID_INDEX.
characterAt has a conditional rather than a loop, so correctness follows by considering the two possible outcomes of the boundary test.
On line 2, the algorithm computes:
1n = length(text)Therefore n is known before the algorithm uses n to decide whether i is valid. In particular, the final valid index, when one exists, is n - 1.
Suppose:
10 <= i < nThen neither part of line 4 is true:
1i < 0
2i >= nSo the algorithm reaches line 7 and returns text[i].
Because i satisfies the valid-index condition, text[i] names exactly one character in the ordered string. Thus the returned value is the requested character.
Suppose i does not satisfy:
10 <= i < nThen either:
1i < 0or:
1i >= nis true. Line 4 detects this, and line 5 returns INVALID_INDEX.
The algorithm does not evaluate text[i] in this case. Therefore it rejects negative indexes and indexes at or beyond the string length.
The algorithm performs a length operation, one boundary test, and one return. It has no loop or recursion. It always reaches either line 5 or line 7.
Therefore, characterAt returns text[i] for every valid index and returns INVALID_INDEX for every invalid index.
For one call to characterAt, after obtaining the length, the shown work is:
INVALID_INDEX, or one indexed read text[i] followed by a return.Under this course’s indexed-string model, reading text[i] performs one indexed access. Therefore a valid character read is:
1O(1) timeThe invalid case also performs a fixed number of checks and returns, so it is likewise:
1O(1) timeThe algorithm stores only:
1nalong with its inputs and return value. Its auxiliary space is:
1O(1)The input string itself is not auxiliary space.
If instead we label or visit every position of a string of length n, we do one constant amount of work for each character:
1position 0: one visit
2position 1: one visit
3...
4position n - 1: one visitThat is n visits, so a full traversal takes:
1O(n) timeA traversal that keeps only a current index and a current character uses:
1O(1) auxiliary spaceIncorrect assumption:
1The first character is text[1].Input that exposes it:
1text = "DOG"
2requested first characterWrong result:
1text[1] = OThe access returns the second character instead of the first.
Correction:
1text[0] = DZero-based indexing means the first character is at index 0.
n as an indexIncorrect boundary check:
1if i > n:
2 return INVALID_INDEXThe condition fails to reject i = n.
Input that exposes it:
1text = "DOG"
2i = 3
3n = 3Wrong state or output:
The implementation may fabricate a fourth character, silently accept an invalid access, or attempt an out-of-range read.
Correction:
1if i < 0 or i >= n:
2 return INVALID_INDEXFor "DOG", valid indexes satisfy:
1i < 3So index 3 must be rejected.
Incorrect assumption:
1length("") = 1Input that exposes it:
1text = ""Wrong result:
1length = 1The result invents a character that is not present.
Correction:
1length("") = 0The empty string has no characters and no valid character index. In particular, text[0] is invalid.
| String | Length | Valid indexes | Example access |
|---|---|---|---|
"" | 0 | none | text[0] is invalid |
"A" | 1 | 0 | text[0] is A; text[1] is invalid |
" " | 2 | 0, 1 | Both spaces are characters |
"aA" | 2 | 0, 1 | text[0] is lowercase a; text[1] is uppercase A |
Executable objective: Given a string text and integer i, return text[i] when:
10 <= i < length(text)Otherwise, return the specified invalid-index result.
The tests will check this contract with:
i = length(text).1INVALID_INDEX = "INVALID_INDEX"
2
3def character_at(text, i):
4 n = len(text)
5 if i < 0 or i >= n: # rejects negatives and i == n
6 return INVALID_INDEX
7 return text[i]
8
9print(character_at("DOG", 1))
10print(character_at("DOG", 3))
11print(character_at("DOG", -1))
12print(character_at("", 0))
13print(" ".join(f"{i}:{c}" for i, c in enumerate("DOG")))1public class Main {
2 static final String INVALID_INDEX = "INVALID_INDEX";
3
4 static String characterAt(String text, int i) {
5 int n = text.length();
6 if (i < 0 || i >= n) return INVALID_INDEX; // rejects negatives and i == n
7 return String.valueOf(text.charAt(i));
8 }
9
10 public static void main(String[] args) {
11 System.out.println(characterAt("DOG", 1));
12 System.out.println(characterAt("DOG", 3));
13 System.out.println(characterAt("DOG", -1));
14 System.out.println(characterAt("", 0));
15 String text = "DOG";
16 StringBuilder sb = new StringBuilder();
17 for (int i = 0; i < text.length(); i++) {
18 if (i > 0) sb.append(' ');
19 sb.append(i).append(':').append(text.charAt(i));
20 }
21 System.out.println(sb);
22 }
23}1#include <iostream>
2#include <string>
3using namespace std;
4
5string characterAt(const string& text, int i) {
6 int n = (int)text.size();
7 if (i < 0 || i >= n) return "INVALID_INDEX"; // rejects negatives and i == n
8 return string(1, text[i]);
9}
10
11int main() {
12 cout << characterAt("DOG", 1) << endl;
13 cout << characterAt("DOG", 3) << endl;
14 cout << characterAt("DOG", -1) << endl;
15 cout << characterAt("", 0) << endl;
16 string text = "DOG";
17 for (int i = 0; i < (int)text.size(); i++) {
18 if (i > 0) cout << ' ';
19 cout << i << ':' << text[i];
20 }
21 cout << endl;
22}1const INVALID_INDEX = 'INVALID_INDEX';
2
3function characterAt(text, i) {
4 const n = text.length;
5 if (i < 0 || i >= n) return INVALID_INDEX; // rejects negatives and i === n
6 return text[i];
7}
8
9console.log(characterAt('DOG', 1));
10console.log(characterAt('DOG', 3));
11console.log(characterAt('DOG', -1));
12console.log(characterAt('', 0));
13console.log([...'DOG'].map((c, i) => `${i}:${c}`).join(' '));"DOG", "aA", "a a" and the empty string "" are all strings. Spaces and punctuation are characters, and "a" and "A" are different characters.
In C# and TypeScript, string[] is an array whose elements are strings, not one string. Java spells it String[]. Each element is a whole string, so names[0] is a string and names[0][0] is a character.
The length is 3, so the valid indexes are 0, 1 and 2. Index 3 sits one past the last character, and the test 3 < 3 is false.
The lesson reads a string as one indexed element per displayed character. A language may store the text as bytes, and the byte position can differ from the character position depending on the encoding.
Zero. It holds no characters, so text[0] is invalid. Treating it as length 1 invents a character that is not there.