Verify Nickname Subsequence — Problem Statement & Solution Guide
Problem Description
Given two strings, fullName and nickname, determine if nickname is a valid subsequence of fullName. A nickname is considered a valid subsequence if it can be derived from fullName by deleting zero or more characters without changing the relative order of the remaining characters. The comparison must be case-insensitive.
Examples
Input
fullName = 'Benjamin', nickname = 'n'
Output
false
Explanation: Step-by-step: We iterate through fullName and nickname. Since 'n' is not present in fullName, we return false.
Input
fullName = 'Sophia', nickname = 'Osa'
Output
false
Explanation: Step-by-step: We iterate through fullName and nickname. Since 'Osa' is not a subsequence of 'Sophia', we return false.
Constraints
- 1 <= fullName.length <= 10^4
- 1 <= nickname.length <= 10^4
- fullName and nickname consist only of uppercase and lowercase English letters.
Optimal Approach & Strategy
The optimal approach is to use two pointers, one for the fullName string and one for the nickname string, to compare characters in order. This approach allows us to find a subsequence in linear time.
Brute Force Approach
One naive approach is to generate all possible subsequences of the fullName string and check if the nickname matches any of them. However, this approach would have a time complexity of O(2^n), where n is the length of the fullName string.
Verified Code Solutions
public boolean isValidSubsequence(String fullName, String nickname) {
int m = fullName.length(), n = nickname.length();
int i = 0, j = 0;
while (i < m && j < n) {
if (Character.toLowerCase(fullName.charAt(i)) == Character.toLowerCase(nickname.charAt(j))) {
j++;
}
i++;
}
return j == n;
}def is_valid_subsequence(full_name, nickname):
m, n = len(full_name), len(nickname)
i, j = 0, 0
while i < m and j < n:
if full_name[i].lower() == nickname[j].lower():
j += 1
i += 1
return j == nAsked 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.