15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
String manipulation means building a new string from an existing one: take a substring, reverse it, join pieces or compare two strings. Every step works on indexed characters, and a half-open range text[start..end) includes start and excludes end. Reversing a range of m characters takes O(m) time when you write into a mutable buffer.
| Substring bounds | 0 <= start <= end <= n, end excluded |
|---|---|
| Read one character or the length | O(1) time |
| Concatenate lengths a and b | O(a + b) time and result storage |
| Reverse a range of m characters | O(m) time, O(m) result, O(1) auxiliary |
| Compare two length-n strings | O(n) worst case, O(1) auxiliary |
| Rebuild an immutable result each step | O(n^2) for a full reverse of length n when each step copies |
The course model treats a string as an indexed sequence of characters.
For a string text:
length(text) is the number of indexed characters.0 through length(text) - 1.text[i] reads one character at index i.A substring range is half-open:
1text[start..end)It includes start and excludes end.
The bounds must satisfy:
10 <= start <= end <= length(text)If end is 3, index 3 is not part of the range.
Use this input throughout:
1text = "BIRD"
2take text[1..3) and reverse itWrite the indexes above the characters.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
text | B | I | R | D |
The requested range is [1, 3).
1.3.1 and 2.The substring is:
1"IR"To reverse "IR", read from its right end.
1source: I R
2index: 0 1
3
4output: R I
5index: 0 1Start with the full indexed string.
text = "BIRD", range [1, 3): the substring is "IR". Reading it from its last index 1 down to 0 builds the reversed copy "RI".
The range begins at 1 and ends before 3.
Indexes 1 and 2 are inside [1, 3).
1substring index: 0 1
2substring: I RThe substring is "IR".
The last valid substring index is:
1length("IR") - 1 = 2 - 1 = 1Read index 1.
1source index = 1
2source[1] = R
3output = "R"Move from index 1 to index 0.
1source index = 0
2source[0] = I
3output = "RI"There are no indexes left to read. The reversed copy is:
1"RI"Watch the output after each character is processed from the source's right side.
For source "IR":
| Characters processed from the right | Output |
|---|---|
| 0 | "" |
1: R | "R" |
2: R, then I | "RI" |
After processing k characters from the right of a source string, the output contains exactly those k processed characters in reverse order.
That property is the loop invariant.
After one step on "IR", only R has been processed. The output is "R", which is the reverse of that processed portion. After two steps, both source characters have been processed, and the output is "RI".
The range must be valid before reading any character.
10 <= start <= end <= length(text)For the example:
10 <= 1 <= 3 <= 4So [1, 3) is valid.
The range length is:
1end - startFor "BIRD" and [1, 3):
13 - 1 = 2Create a mutable output buffer with two positions. Fill it from left to right.
To reverse the range:
end - 1, the last character included in the range.text[sourceIndex].start.For [1, 3), the source indexes are visited in this order:
12, 1Those characters are:
1R, IThe output becomes:
1RIreverseRange returns a newly constructed string. It does not mutate text.
Helper contracts:
length(text) returns the number of indexed characters in text.newCharacterArray(n) creates a mutable character array with positions 0 through n - 1.joinCharacters(buffer) returns a string containing the buffer's characters in index order.reject stops the operation because the requested range is invalid.1function reverseRange(text, start, end) -> string
2 # Input:
3 # text: an indexed string
4 # start, end: requested half-open range bounds
5 # Return:
6 # a new string containing text[start..end) in reverse order
7 # Mutation:
8 # does not modify text; writes only into a new local buffer
9
101. n <- length(text)
11
122. if start < 0 or start > end or end > n
133. reject "invalid substring bounds"
14
154. rangeLength <- end - start
165. output <- newCharacterArray(rangeLength)
17
186. sourceIndex <- end - 1
197. outputIndex <- 0
20
218. while sourceIndex >= start
229. output[outputIndex] <- text[sourceIndex]
2310. sourceIndex <- sourceIndex - 1
2411. outputIndex <- outputIndex + 1
25
2612. return joinCharacters(output)The loop has no iterations for an empty range. If start = end, then:
1sourceIndex = end - 1is less than start, so the loop condition is false immediately.
Run:
1reverseRange("BIRD", 1, 3)| Line | State or action |
|---|---|
| 1 | n <- length("BIRD"), so n = 4. |
| 2 | Check start < 0: 1 < 0 is false. |
| 2 | Check start > end: 1 > 3 is false. |
| 2 | Check end > n: 3 > 4 is false. |
| 4 | rangeLength <- 3 - 1, so rangeLength = 2. |
| 5 | Create output with indexes 0 and 1. |
| 6 | sourceIndex <- 3 - 1, so sourceIndex = 2. |
| 7 | outputIndex <- 0. |
| 8 | Check 2 >= 1: true. Enter the loop. |
| 9 | output[0] <- text[2]. text[2] is R. Output is now [R, _]. |
| 10 | sourceIndex <- 2 - 1, so sourceIndex = 1. |
| 11 | outputIndex <- 0 + 1, so outputIndex = 1. |
| 8 | Check 1 >= 1: true. Enter the loop. |
| 9 | output[1] <- text[1]. text[1] is I. Output is now [R, I]. |
| 10 | sourceIndex <- 1 - 1, so sourceIndex = 0. |
| 11 | outputIndex <- 1 + 1, so outputIndex = 2. |
| 8 | Check 0 >= 1: false. Leave the loop. |
| 12 | joinCharacters([R, I]) returns "RI". |
The result is:
1"RI"Assume the bounds pass the validation check. Then:
10 <= start <= end <= length(text)So every index from start through end - 1 is valid.
The loop invariant is:
After processing
kcharacters from the right oftext[start..end),output[0..k)contains thosekcharacters in reverse order.
Before the loop:
1sourceIndex = end - 1
2outputIndex = 0No source characters have been processed. The output contains zero characters. Therefore, the invariant holds for k = 0.
Suppose the invariant holds at the beginning of an iteration.
sourceIndex points to the next unprocessed character from the right side of the range. Line 9 copies that character into output[outputIndex], immediately after the already constructed output characters.
Then:
sourceIndex left by one,outputIndex by one.Exactly one new rightmost unprocessed source character has been appended. The output now contains one more character in the required reversed order. The invariant is preserved.
The loop stops when:
1sourceIndex < startAt that point, every index in the range [start, end) has been processed exactly once.
The range contains:
1end - startcharacters. By the invariant, the output contains all of them in reverse order. Therefore, reverseRange(text, start, end) returns the reverse of text[start..end).
For equality, a separate whole-string comparison must establish both conditions:
Matching lengths alone do not establish string equality.
Reading one valid indexed character is O(1) in the indexed course model.
Reading a string's length is also O(1) in this model.
If two sequences have lengths a and b, concatenating them constructs a + b output characters. One such construction takes:
1O(a + b) time
2O(a + b) result storagereverseRangeFor a range of length:
1m = end - startthe loop runs once for each character in the requested range.
For "BIRD" and [1, 3):
1m = 3 - 1 = 2The loop performs two character reads and two buffer writes:
1source index 2 -> output index 0
2source index 1 -> output index 1In general, reversing a range of length m takes:
1O(m) timeThe returned output contains m characters, so result storage is:
1O(m)The local indexes use constant extra temporary space. Excluding the returned result, auxiliary space is:
1O(1)For a full string of length n, m = n, so reversal is O(n) time and requires O(n) result storage.
A direct equality comparison first needs matching lengths. If lengths match, it may compare every character pair.
For two length-n strings that differ only at the final position, all n pairs may be checked. Its worst-case time is:
1O(n)It uses:
1O(1) temporary auxiliary spaceRepeatedly rebuilding an immutable result can copy prior output again and again.
For a full reverse of "BIRD", repeated construction could create:
1""
2"D"
3"DR"
4"DRI"
5"DRIB"The copied prefix lengths can be:
10 + 1 + 2 + 3For length n, the sum grows as:
11 + 2 + ... + nwhich gives O(n^2) time. Writing each character once into a preallocated mutable buffer keeps the reverse construction at O(n) time.
Incorrect assumption
1text[start..end) includes endInput
1text = "BIRD"
2range = [1, 3)Wrong result
Taking indexes 1, 2, and 3 produces:
1"IRD"Correction
The end is excluded. [1, 3) includes only indexes 1 and 2, producing:
1"IR"nIncorrect line
1sourceIndex <- nInput
1text = "AB"n is 2, but valid indexes are only 0 and 1.
Wrong state
1text[2]is an invalid access.
Correction
Start at the last valid index:
1sourceIndex <- n - 1For "AB", begin at index 1.
Incorrect test
1return length(left) = length(right)Input
1left = "ab"
2right = "cd"Wrong result
Both lengths are 2, so the test returns equal.
Correction
After lengths match, compare corresponding character positions:
1left[0] with right[0]
2left[1] with right[1]The first pair is a and c, so the strings are not equal.
Incorrect construction idea
1output <- output + text[sourceIndex]when each output is immutable and a new string must be created each time.
Input that exposes it
A long input.
Wrong work pattern
Each step may copy the old output before adding one character. The copied prefixes accumulate.
Correction
Allocate a mutable character array for the result and write each reversed character into its final output position.
| Input | Expected behavior |
|---|---|
text = "", range [0, 0) | substring is ""; reverse is "". |
text = "A", range [0, 1) | substring and reverse are "A". |
text = "BIRD", range [2, 2) | substring and reverse are "". |
text = "BIRD", range [3, 2) | reject because start > end. |
text = "BIRD", range [1, 5) | reject because end > length(text). |
Implement:
1reverseRange(text, start, end)Contract to test:
Return the reverse of text[start..end).
Treat the range as half-open: include start, exclude end.
Reject bounds unless:
10 <= start <= end <= length(text)Do not mutate text.
Construct the returned characters through a mutable buffer or character array.
Tests include empty ranges, full ranges, one-character ranges, and invalid start/end pairs.
1def reverse_range(text, start, end):
2 n = len(text)
3 if start < 0 or start > end or end > n:
4 raise ValueError("invalid substring bounds")
5 output = [""] * (end - start) # mutable buffer, filled left to right
6 source_index = end - 1
7 output_index = 0
8 while source_index >= start:
9 output[output_index] = text[source_index]
10 source_index -= 1
11 output_index += 1
12 return "".join(output)
13
14def equal(left, right):
15 if len(left) != len(right): # lengths first, then every pair
16 return False
17 for i in range(len(left)):
18 if left[i] != right[i]:
19 return False
20 return True
21
22print(reverse_range("BIRD", 1, 3))
23print(reverse_range("BIRD", 0, 4))
24try:
25 reverse_range("BIRD", 1, 5)
26except ValueError as e:
27 print(e)
28print("true" if equal("ab", "cd") else "false")
29print("true" if equal("ab", "ab") else "false")1public class Main {
2 static String reverseRange(String text, int start, int end) {
3 int n = text.length();
4 if (start < 0 || start > end || end > n) {
5 throw new IllegalArgumentException("invalid substring bounds");
6 }
7 char[] output = new char[end - start]; // mutable buffer, filled left to right
8 int sourceIndex = end - 1;
9 int outputIndex = 0;
10 while (sourceIndex >= start) {
11 output[outputIndex] = text.charAt(sourceIndex);
12 sourceIndex--;
13 outputIndex++;
14 }
15 return new String(output);
16 }
17
18 static boolean equal(String left, String right) {
19 if (left.length() != right.length()) return false; // lengths first, then every pair
20 for (int i = 0; i < left.length(); i++) {
21 if (left.charAt(i) != right.charAt(i)) return false;
22 }
23 return true;
24 }
25
26 public static void main(String[] args) {
27 System.out.println(reverseRange("BIRD", 1, 3));
28 System.out.println(reverseRange("BIRD", 0, 4));
29 try {
30 reverseRange("BIRD", 1, 5);
31 } catch (IllegalArgumentException e) {
32 System.out.println(e.getMessage());
33 }
34 System.out.println(equal("ab", "cd") ? "true" : "false");
35 System.out.println(equal("ab", "ab") ? "true" : "false");
36 }
37}1#include <iostream>
2#include <stdexcept>
3#include <string>
4using namespace std;
5
6string reverseRange(const string& text, int start, int end) {
7 int n = (int)text.size();
8 if (start < 0 || start > end || end > n) {
9 throw invalid_argument("invalid substring bounds");
10 }
11 string output(end - start, ' '); // mutable buffer, filled left to right
12 int sourceIndex = end - 1;
13 int outputIndex = 0;
14 while (sourceIndex >= start) {
15 output[outputIndex] = text[sourceIndex];
16 sourceIndex--;
17 outputIndex++;
18 }
19 return output;
20}
21
22bool equalStrings(const string& left, const string& right) {
23 if (left.size() != right.size()) return false; // lengths first, then every pair
24 for (size_t i = 0; i < left.size(); i++) {
25 if (left[i] != right[i]) return false;
26 }
27 return true;
28}
29
30int main() {
31 cout << reverseRange("BIRD", 1, 3) << endl;
32 cout << reverseRange("BIRD", 0, 4) << endl;
33 try {
34 reverseRange("BIRD", 1, 5);
35 } catch (const invalid_argument& e) {
36 cout << e.what() << endl;
37 }
38 cout << (equalStrings("ab", "cd") ? "true" : "false") << endl;
39 cout << (equalStrings("ab", "ab") ? "true" : "false") << endl;
40}1function reverseRange(text, start, end) {
2 const n = text.length;
3 if (start < 0 || start > end || end > n) {
4 throw new Error('invalid substring bounds');
5 }
6 const output = new Array(end - start); // mutable buffer, filled left to right
7 let sourceIndex = end - 1;
8 let outputIndex = 0;
9 while (sourceIndex >= start) {
10 output[outputIndex] = text[sourceIndex];
11 sourceIndex--;
12 outputIndex++;
13 }
14 return output.join('');
15}
16
17function equal(left, right) {
18 if (left.length !== right.length) return false; // lengths first, then every pair
19 for (let i = 0; i < left.length; i++) {
20 if (left[i] !== right[i]) return false;
21 }
22 return true;
23}
24
25console.log(reverseRange('BIRD', 1, 3));
26console.log(reverseRange('BIRD', 0, 4));
27try {
28 reverseRange('BIRD', 1, 5);
29} catch (e) {
30 console.log(e.message);
31}
32console.log(equal('ab', 'cd') ? 'true' : 'false');
33console.log(equal('ab', 'ab') ? 'true' : 'false');Take "BIRD" and the range [1, 3). The substring is "IR" (indexes 1 and 2). Reading it from the right gives "RI". The original "BIRD" is not modified.
The Python program above is one. It validates the bounds, writes characters from the end of the range into a list, and joins the list. For the input "BIRD" with [1, 3) it prints RI.
Both are C library functions on null-terminated strings. The function strlen returns the number of characters before the terminating null. The function strcpy copies a string into a buffer, and it does not check that the buffer is large enough.
When each result is immutable, every step can copy the whole output so far. For length n the copied prefixes add up to 1 + 2 + ... + n, which is O(n^2). A preallocated buffer written once per character is O(n).
Compare the lengths first, then compare every pair of characters at the same index. Equal lengths alone prove nothing: "ab" and "cd" both have length 2. The worst case is O(n) when the strings differ only at the end.
No. text[1..3) includes indexes 1 and 2 and excludes 3. Including the end turns "IR" into "IRD" for "BIRD".