String Reversal Check — Problem Statement & Solution Guide
Problem Description
You are provided with two strings, s and t. Your task is to determine whether t is the exact reverse of s. Specifically, you must verify if the sequence of characters in t matches the sequence of characters in s when read from the last character to the first.
The comparison is case-sensitive. For example, 'A' and 'a' are considered distinct characters. If the lengths of the two strings differ, the result is immediately false, as a reversal must preserve the length of the original string.
Return true if t is the reversal of s, and false otherwise.
DSA Pattern Breakdown
DSA Pattern Breakdown
"String Reversal Check"
WHY DOES IT MATTER?
The two‑pointer reverse comparison pattern is essential because it transforms a potentially quadratic or memory‑heavy operation into a linear, constant‑space one. This is especially valuable in systems where latency and memory footprint directly impact user experience or cost, such as real‑time data pipelines or mobile applications.
OPTIMIZATION CHALLENGE
The key insight is that you can compare characters from opposite ends simultaneously, eliminating the need to construct a reversed string. This reduces both time (no extra pass) and space (no auxiliary array) complexity.
REAL-WORLD CONNECTION
Consider a distributed log replication system where a leader must verify that a follower’s log is the exact reverse of its own for rollback purposes. Using a two‑pointer check allows the system to confirm consistency without copying the entire log, preserving bandwidth and reducing the risk of network congestion.
When presenting this solution in an interview, emphasize the two‑pointer technique as a classic example of in‑place algorithm design. Highlight that it showcases your ability to think about memory usage and to apply a proven pattern to a new problem.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of checking whether one string is the reverse of another boils down to a linear scan of both strings from opposite ends. In the naive approach, one might first reverse the first string using a built‑in function or a loop, then compare it to the second string. This incurs an extra O(n) time for the reversal and O(n) auxiliary space to store the reversed copy, which becomes costly for very long inputs or memory‑constrained environments. The optimal paradigm eliminates the need for an intermediate reversed string by simultaneously iterating over the original string from the start and the second string from the end, comparing corresponding characters on the fly. This single pass guarantees O(n) time while keeping space usage to O(1), making it suitable for large datasets and streaming scenarios where memory is at a premium.
Beyond the immediate algorithmic efficiency, this pattern exemplifies a broader class of problems where symmetry or reverse relationships are involved—such as palindrome detection, two‑pointer techniques on arrays, or bidirectional traversal in graph algorithms. Recognizing that a reverse comparison can be performed in place allows engineers to write cleaner, more performant code and to avoid unnecessary allocations that could trigger garbage collection or memory fragmentation in high‑throughput systems.
Interview Questions on This Problem
Q1What is the most efficient way to determine if string t is the reverse of string s, and why is it preferred over reversing s first?
The most efficient method is to use two pointers: one starting at the beginning of s and the other at the end of t, moving inward while comparing characters. This approach runs in O(n) time and O(1) space, avoiding the extra O(n) space needed to store a reversed copy of s, which is critical for large inputs and memory‑constrained environments.
Q2How would you modify the algorithm if the strings could contain Unicode characters that are represented by surrogate pairs in UTF‑16?
You would need to iterate over code points rather than code units. In languages like Java, use the String.codePointAt and codePointCount methods, or in Python, iterate over the string directly as it handles Unicode code points natively. This ensures that characters like emojis are treated as single units during comparison.
Q3During a coding interview at a fintech startup, the interviewer asks you to explain the time and space complexity of your solution. What key points should you mention?
Explain that the algorithm performs a single linear scan of the strings, so the time complexity is O(n), where n is the length of the strings (assuming they are equal). For space, you only use a few integer variables for indices, so the space complexity is O(1). If you had used a reversed copy, it would have been O(n) space, which is why the two‑pointer approach is preferred.
Examples
Input
s = "abcde", t = "edcba"
Output
true
Explanation: The length of both strings is 5. Reversing "abcde" yields "edcba", which is identical to `t`. Therefore, the output is true.
Input
s = "hello", t = "olleh"
Output
true
Explanation: The length of both strings is 5. Reversing "hello" yields "olleh", which matches `t`. Therefore, the output is true.
Input
s = "python", t = "nohtyp"
Output
false
Explanation: The length of both strings is 6. Reversing "python" yields "nohtyp". However, `t` is "nohtyp". Wait, let me re-verify. Reversing "python" is "nohtyp". The input `t` is "nohtyp". This would be true. Let me create a false case. Revised Input: s = "python", t = "nohtpy" Revised Explanation: The length of both strings is 6. Reversing "python" yields "nohtyp". The string `t` is "nohtpy", which does not match the reversed string. Therefore, the output is false.
Input
s = "a", t = "b"
Output
false
Explanation: The length of both strings is 1. Reversing "a" yields "a". The string `t` is "b", which does not match "a". Therefore, the output is false.
Input
s = "ab", t = "ba"
Output
true
Explanation: The length of both strings is 2. Reversing "ab" yields "ba", which is identical to `t`. Therefore, the output is true.
Constraints
- 1 <= s.length, t.length <= 10^5
- s and t consist of lowercase and uppercase English letters and digits.
- The total length of s and t across all test cases does not exceed 10^6.
Optimal Approach & Strategy
The optimal approach uses two pointers: one at the start of the first string and one at the end of the second string, comparing characters on the fly. This runs in O(n) time and O(1) space, avoiding any extra storage.
Brute Force Approach
A naive approach is to reverse the first string using a built‑in function or a loop, then compare the reversed string to the second string. This requires O(n) time for the reversal and O(n) extra space to store the reversed copy.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let idx = 0;
const s = input[idx++];
const t = input[idx++];
function isReverse(s, t) {
return s === t.split('').reverse().join('');
}
console.log(isReverse(s, t) ? 'true' : 'false');#include <bits/stdc++.h>
using namespace std;
bool isReverse(const string& s, const string& t) {
return s == string(t.rbegin(), t.rend());
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
if (!(cin >> s)) return 0;
if (!(cin >> t)) return 0;
cout << (isReverse(s, t) ? "true" : "false");
return 0;
}
import java.util.*;
public class Main {
public static boolean isReverse(String s, String t) {
return s.equals(new StringBuilder(t).reverse().toString());
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNext()) return;
String s = sc.next();
if (!sc.hasNext()) return;
String t = sc.next();
System.out.print(isReverse(s, t) ? "true" : "false");
}
}
import sys
def is_reverse(s: str, t: str) -> bool:
return s == t[::-1]
if __name__ == "__main__":
data = sys.stdin.read().strip().split()
if len(data) < 2:
sys.exit()
s, t = data[0], data[1]
print("true" if is_reverse(s, t) else "false")
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let idx = 0;
const s = input[idx++];
const t = input[idx++];
function isReverse(s, t) {
return s === t.split('').reverse().join('');
}
console.log(isReverse(s, t) ? 'true' : 'false');
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.