Reverse Prefix of Word — Solution in Python, Java & C++
Reverse Prefix of Word solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Reverse Prefix of Word is an easy coding problem on strings, two pointers and stack, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Two Pointers, Stack
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string word and a single character ch, reverse the segment of word that starts at index 0 and ends at the first occurrence of ch (inclusive).
If ch does not occur in word, return word unchanged.
Example 1
Input: word = "abcdefd", ch = "d"
Output: dcbaefd
Explanation: The first d is at index 3, so "abcd" reverses to "dcba".
Example 2
Input: word = "xyxzxe", ch = "z"
Output: zxyxxe
Example 3
Input: word = "abcd", ch = "z"
Output: abcd
Constraints
1 <= word.length <= 40word consists of lowercase English letters.ch is a single lowercase English letter.
Hints for Reverse Prefix of Word
Hint 1
Find the first index of
ch— a missing character means there is nothing to do.Hint 2
Reverse the slice up to and including that index, then append the rest untouched.
How to solve Reverse Prefix of Word
Find the first ch; reverse the prefix through that index and keep the rest.
Approach
- Locate
idx = word.find(ch); returnwordif-1. - Return
reverse(word[:idx+1]) + word[idx+1:].
Why it works
The statement defines the segment as index 0 through the first occurrence inclusive; everything after it is untouched.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Include the matched character in the reversed slice.
Reference solution
Python
def reversePrefix(word: str, ch: str) -> str:
idx = word.find(ch)
if idx < 0:
return word
return word[:idx + 1][::-1] + word[idx + 1:]Java
public static String reversePrefix(String word, String ch) {
int idx = word.indexOf(ch);
if (idx < 0) return word;
String head = new StringBuilder(word.substring(0, idx + 1)).reverse().toString();
return head + word.substring(idx + 1);
}C++
string reversePrefix(string word, string ch) {
size_t idx = word.find(ch);
if (idx == string::npos) return word;
reverse(word.begin(), word.begin() + idx + 1);
return word;
}JavaScript
var reversePrefix = function(word, ch) {
const idx = word.indexOf(ch);
if (idx < 0) return word;
return word.slice(0, idx + 1).split("").reverse().join("") + word.slice(idx + 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique