Leetcode 1638: Count Substrings That Differ by One Character
Given two strings s and t, count the number of ways to choose a non-empty substring of s and replace exactly one character such that the resulting substring becomes a substring of t. In other words, find how many substrings in s differ from substrings in t by exactly one character.
Problem
Approach
Steps
Complexity
Input: The input consists of two strings s and t. Both strings are lowercase English letters.
Example: s = "cat", t = "bat"
Constraints:
• 1 <= s.length, t.length <= 100
• s and t consist of lowercase English letters only.
Output: The output is the number of substrings in s that differ from some substring in t by exactly one character.
Example: Output: 3
Constraints:
• The output will be a non-negative integer.
Goal: The goal is to count how many substrings in s differ by exactly one character from substrings in t.
Steps:
• Iterate over all possible substrings of s and t.
• For each pair of substrings, check if they differ by exactly one character.
• Count the number of valid substring pairs.
Goal: The length of the strings s and t is between 1 and 100, and both consist of lowercase English letters.
Steps:
• 1 <= s.length, t.length <= 100
• s and t consist of lowercase English letters only.
Assumptions:
• The strings s and t will always contain at least one character.
• Input: s = "cat", t = "bat"
• Explanation: The substrings that differ by exactly one character are 'cat' vs 'bat', which gives a count of 3.
Approach: We will solve this problem by iterating through all possible substrings of s and t, checking if they differ by exactly one character, and counting those pairs.
Observations:
• Checking every pair of substrings from s and t is a brute force approach.
• Optimizing the approach to check for only those substrings that are similar in size might improve performance.
Steps:
• Generate all substrings of s and t.
• For each pair of substrings, compare them character by character to count how many characters differ.
• If exactly one character differs, increase the count.
Empty Inputs:
• Both strings will have at least one character, so no need to handle empty inputs.
Large Inputs:
• For large inputs, the algorithm may need optimization to avoid exceeding time limits.
Special Values:
• Substrings of length 1 should be handled carefully.
Constraints:
• Ensure that the algorithm works for all valid lengths of strings.
int countSubstrings(string s, string t) {
int res = 0;
for(int i = 0; i < s.size(); i++)
res += helper(s, t, i, 0);
for(int j = 1; j < t.size(); j++)
res += helper(s, t, 0, j);
return res;
}
int helper(string s, string t, int i, int j) {
int res = 0, pre = 0, cur = 0;
for(int n = s.size(), m = t.size(); i < n && j < m; i++, j++) {
cur++;
if(s[i] != t[j]) {
pre = cur;
cur = 0;
}
res += pre;
}
return res;
}
1 : Method Definition
int countSubstrings(string s, string t) {
Define the method 'countSubstrings' that takes two strings, 's' and 't', as input and calculates the number of matching substrings.
2 : Variable Initialization
int res = 0;
Initialize a result variable 'res' to store the total count of matching substrings.
3 : Loop Constructs
for(int i = 0; i < s.size(); i++)
Start a loop that iterates over the string 's' from the first to the last character.
4 : Function Call
res += helper(s, t, i, 0);
Call the helper function for each starting position 'i' in string 's' and fixed starting position 0 in string 't'.
5 : Loop Constructs
for(int j = 1; j < t.size(); j++)
Start another loop that iterates over the string 't' from the second character to the last.
6 : Function Call
res += helper(s, t, 0, j);
Call the helper function for each starting position 'j' in string 't' and fixed starting position 0 in string 's'.
7 : Return Statement
return res;
Return the final result, which is the total number of matching substrings.
8 : Helper Function Definition
int helper(string s, string t, int i, int j) {
Define the helper function that counts matching substrings starting from the given positions 'i' in string 's' and 'j' in string 't'.
9 : Variable Initialization
int res = 0, pre = 0, cur = 0;
Initialize variables 'res' for the total count of matches, 'pre' for tracking previous matches, and 'cur' for the current matching length.
10 : Loop Constructs
for(int n = s.size(), m = t.size(); i < n && j < m; i++, j++) {
Start a loop that iterates over the strings 's' and 't' as long as both indices 'i' and 'j' are within the bounds of their respective strings.
11 : Mathematical Operations
cur++;
Increment the 'cur' variable as we find a matching character at the current positions 'i' and 'j'.
12 : Conditional Statement
if(s[i] != t[j]) {
Check if the characters at positions 'i' in string 's' and 'j' in string 't' do not match.
13 : Variable Update
pre = cur;
If the characters don't match, store the value of 'cur' (the length of the previous match) in 'pre'.
14 : Variable Reset
cur = 0;
Reset 'cur' to 0 because the match was broken.
15 : Mathematical Operations
res += pre;
Add the value of 'pre' (previous match length) to 'res'.
16 : Return Statement
return res;
Return the total number of matching substrings found by the helper function.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) because we are generating and comparing all possible substrings.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) due to storing all possible substrings.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus