Count Substrings That Differ by One Character solution and explanation
9 more videos on this problem
Leetcode 1638 Count Substrings That Differ by One CharacterFraz · 10:20 · 11K views
1638.Count Substrings That Differ by One Character|leetcode dp series|leetcodeDp wale · 9:00 · 2K views
15. Count Substrings That Differ by One Character | 3d-DP | LeetCode Medium 1638AceCoder Academy · 40:43 · 1K views
1638. Count Substrings That Differ by One Character (Leetcode Medium)Programming Live with Larry · 11:00 · 1K views
【每日一题】1638. Count Substrings That Differ by One Character, 11/1/2020Huifeng Guan · 21:36 · 1K views
Leetcode 1638. Count Substrings That Differ by One CharacterElite Code · 16:57 · 925 views
Leetcode 1638. Count Substrings That Differ by One CharacterFearless Learner · 7:22 · 194 views
LeetCode Biweekly Contest 38 Problem C: Count Substrings That Differ by One CharacterTheCodeBakery Tutorials · 8:13 · 159 views
Code Review: LeetCode 1638: Count Substrings That Differ by One CharacterRoel Van de Paar · 2:59 · 67 views
Leetcode 1638. Count Substrings That Differ by One Character(brute force)LetsCode · 10:16 · 44 views
The problem
Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.
For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.
Return the number of substrings that satisfy the condition above.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.
Example 2:
Input: s = "ab", t = "bb"
Output: 3
Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
("ab", "bb")
("ab", "bb")
("ab", "bb")
The underlined portions are the substrings that are chosen from s and t.
Constraints:
1 <= s.length, t.length <= 100sandtconsist of lowercase English letters only.
Approach overview
Problem Overview: Given two strings s and t, count how many substring pairs (one from each string) differ by exactly one character. The substrings must be the same length, and only a single position is allowed to mismatch.
Approach 1: Naive Approach Using Substring Comparison (O(n^3) time, O(1) space)
The brute force strategy generates every possible substring from s and t with the same length and compares them character by character. For each starting index i in s and j in t, iterate through the substring length and count mismatches. If exactly one mismatch occurs, increment the answer. This approach relies purely on string traversal and direct character comparison. While simple and easy to reason about, the repeated comparisons make the time complexity roughly O(n^3) in the worst case when many substrings share similar prefixes.
Approach 2: Optimized Approach Using Dynamic Sliding Window (O(n * m) time, O(1) space)
A more efficient strategy aligns the strings using diagonal traversal and expands a sliding window along each alignment. Start with offsets between s and t. For every aligned pair of indices, walk forward while tracking the positions of mismatches. Maintain two pointers: one marking the start of the current window and another tracking the last mismatch. When a second mismatch appears, shift the window start to the position after the previous mismatch. Every step counts how many substrings ending at the current position contain exactly one mismatch. This converts repeated substring comparisons into a single pass along each alignment. The technique combines ideas from dynamic programming and window-based enumeration over string indices, reducing the complexity to O(n * m) while using constant extra space.
Recommended for interviews: Start by explaining the brute force substring comparison since it demonstrates the core observation: count substrings with exactly one mismatch. Interviewers typically expect the optimized diagonal sliding-window method. It eliminates redundant comparisons and achieves O(n * m) time with O(1) space, which is optimal for this problem size.
Approach 1: Naive Approach Using Substring Comparison
This approach involves generating all possible substrings of both strings s and t and then comparing them. For each pair of substrings, check if they differ by exactly one character and count those pairs.
def countSubstrings(s, t):
count = 0
for i in range(len(s)):
for j in range(len(t)):
miss = 0
k = 0
while i + k < len(s) and j + k < len(t):
if s[i + k] != t[j + k]:
miss += 1
if miss == 1:
count += 1
if miss > 1:
break
k += 1
return count
s = "aba"
t = "baba"
print(countSubstrings(s, t))public class Main {
public static int countSubstrings(String s, String t) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < t.length(); j++) {
int miss = 0;
for (int k = 0; i + k < s.length() && j + k < t.length(); k++) {
if (s.charAt(i + k) != t.charAt(j + k)) miss++;
if (miss == 1) count++;
if (miss > 1) break;
}
}
}
return count;
}
public static void main(String[] args) {
String s = "aba";
String t = "baba";
System.out.println(countSubstrings(s, t));
}
}#include <iostream>
#include <string>
int countSubstrings(std::string s, std::string t) {
int count = 0;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < t.size(); j++) {
int miss = 0;
for (int k = 0; i + k < s.size() && j + k < t.size(); k++) {
if (s[i + k] != t[j + k]) miss++;
if (miss == 1) count++;
if (miss > 1) break;
}
}
}
return count;
}
int main() {
std::string s = "aba";
std::string t = "baba";
std::cout << countSubstrings(s, t) << std::endl;
return 0;
}function countSubstrings(s, t) {
let count = 0;
for (let i = 0; i < s.length; i++) {
for (let j = 0; j < t.length; j++) {
let miss = 0;
for (let k = 0; i + k < s.length && j + k < t.length; k++) {
if (s[i + k] !== t[j + k]) miss++;
if (miss === 1) count++;
if (miss > 1) break;
}
}
}
return count;
}
const s = "aba";
const t = "baba";
console.log(countSubstrings(s, t));#include <stdio.h>
#include <string.h>
int countSubstrings(char *s, char *t) {
int count = 0;
int s_length = strlen(s);
int t_length = strlen(t);
for (int i = 0; i < s_length; i++) {
for (int j = 0; j < t_length; j++) {
int miss = 0;
for (int k = 0; i + k < s_length && j + k < t_length; k++) {
if (s[i + k] != t[j + k]) {
miss++;
}
if (miss == 1) {
count++;
}
if (miss > 1) {
break;
}
}
}
}
return count;
}
int main() {
char s[] = "aba";
char t[] = "baba";
printf("%d", countSubstrings(s, t));
return 0;
}using System;
class Program {
public static int CountSubstrings(string s, string t) {
int count = 0;
for (int i = 0; i < s.Length; i++) {
for (int j = 0; j < t.Length; j++) {
int miss = 0;
for (int k = 0; i + k < s.Length && j + k < t.Length; k++) {
if (s[i + k] != t[j + k]) miss++;
if (miss == 1) count++;
if (miss > 1) break;
}
}
}
return count;
}
static void Main() {
string s = "aba";
string t = "baba";
Console.WriteLine(CountSubstrings(s, t));
}
}The Python solution utilizes nested loops to iterate through all possible substrings of s and t. For each substring pair, it calculates the number of character mismatches. If exactly one mismatch is detected, it increments the count.
The time complexity is O(n^2 * m^2), while the space complexity remains O(1), similar to other versions.
Approach 2: Optimized Approach Using Dynamic Sliding Window
An optimized solution is possible by using a dynamic sliding window technique. As we generate substrings of s and t with one mismatch, build them dynamically and count the substrings that are different by exactly one character.
def countSubstrings(s, t):
count = 0
for i in range(len(s)):
for j in range(len(t)):
left = right = 0
while i - left >= 0 and j - left >= 0 and s[i - left] == t[j - left]:
left += 1
while i + right < len(s) and j + right < len(t) and s[i + right] == t[j + right]:
right += 1
if s[i] != t[j]:
count += (left + 1) * (right + 1)
return count
s = "aba"
t = "baba"
print(countSubstrings(s, t))public class Main {
public static int countSubstrings(String s, String t) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < t.length(); j++) {
int left = 0, right = 0, mismatch = 0;
while (i - left >= 0 && j - left >= 0 && s.charAt(i - left) == t.charAt(j - left)) {
left++;
}
while (i + right < s.length() && j + right < t.length() && s.charAt(i + right) == t.charAt(j + right)) {
right++;
}
if (s.charAt(i) != t.charAt(j)) {
count += (left + 1) * (right + 1);
}
}
}
return count;
}
public static void main(String[] args) {
String s = "aba";
String t = "baba";
System.out.println(countSubstrings(s, t));
}
}#include <iostream>
#include <string>
int countSubstrings(std::string s, std::string t) {
int count = 0;
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < t.size(); j++) {
int left = 0, right = 0, mismatch = 0;
while (i - left >= 0 && j - left >= 0 && s[i - left] == t[j - left]) {
left++;
}
while (i + right < s.size() && j + right < t.size() && s[i + right] == t[j + right]) {
right++;
}
if (s[i] != t[j]) {
count += (left + 1) * (right + 1);
}
}
}
return count;
}
int main() {
std::string s = "aba";
std::string t = "baba";
std::cout << countSubstrings(s, t) << std::endl;
return 0;
}function countSubstrings(s, t) {
let count = 0;
for (let i = 0; i < s.length; i++) {
for (let j = 0; j < t.length; j++) {
let left = 0, right = 0;
while (i - left >= 0 && j - left >= 0 && s[i - left] === t[j - left]) {
left++;
}
while (i + right < s.length && j + right < t.length && s[i + right] === t[j + right]) {
right++;
}
if (s[i] !== t[j]) {
count += (left + 1) * (right + 1);
}
}
}
return count;
}
const s = "aba";
const t = "baba";
console.log(countSubstrings(s, t));#include <stdio.h>
#include <string.h>
int countSubstrings(char *s, char *t) {
int count = 0;
int s_length = strlen(s);
int t_length = strlen(t);
for (int i = 0; i < s_length; i++) {
for (int j = 0; j < t_length; j++) {
int left = 0, right = 0, mismatch = 0;
while (i - left >= 0 && j - left >= 0 && s[i - left] == t[j - left]) {
left++;
}
while (i + right < s_length && j + right < t_length && s[i + right] == t[j + right]) {
right++;
}
if (s[i] != t[j]) {
count += (left + 1) * (right + 1);
}
}
}
return count;
}
int main() {
char s[] = "aba";
char t[] = "baba";
printf("%d", countSubstrings(s, t));
return 0;
}using System;
class Program {
public static int CountSubstrings(string s, string t) {
int count = 0;
for (int i = 0; i < s.Length; i++) {
for (int j = 0; j < t.Length; j++) {
int left = 0, right = 0;
while (i - left >= 0 && j - left >= 0 && s[i - left] == t[j - left]) {
left++;
}
while (i + right < s.Length && j + right < t.Length && s[i + right] == t[j + right]) {
right++;
}
if (s[i] != t[j]) {
count += (left + 1) * (right + 1);
}
}
}
return count;
}
static void Main() {
string s = "aba";
string t = "baba";
Console.WriteLine(CountSubstrings(s, t));
}
}This Python solution leverages a dynamic approach to examine mismatches effectively. It adjusts left and right windows around each potential mismatch, counting valid substring pairs based on those windows.
The time complexity is O(n * m), and the space complexity stays at O(1).
Approach 3: Default Approach
func countSubstrings(s string, t string) (ans int) {
m, n := len(s), len(t)
for i, a := range s {
for j, b := range t {
if a != b {
l, r := 0, 0
for i > l && j > l && s[i-l-1] == t[j-l-1] {
l++
}
for i+r+1 < m && j+r+1 < n && s[i+r+1] == t[j+r+1] {
r++
}
ans += (l + 1) * (r + 1)
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach Using Substring Comparison | The time complexity is O(n^2 * m^2), while the space complexity remains O(1), similar to other versions. |
| Optimized Approach Using Dynamic Sliding Window | The time complexity is O(n * m), and the space complexity stays at O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Substring Comparison | O(n^3) | O(1) | Useful for understanding the problem or when input sizes are very small |
| Dynamic Sliding Window / Diagonal Traversal | O(n * m) | O(1) | Best general solution; avoids redundant substring comparisons |
Frequently asked questions
Is Count Substrings That Differ by One Character easy or hard?
The problem is rated Medium because the brute force idea is straightforward but inefficient. The challenge is recognizing the diagonal traversal and sliding window technique that avoids repeated substring comparisons. Once the mismatch-tracking idea is clear, the implementation becomes manageable.
Count Substrings That Differ by One Character Python/Java solution
Both Python and Java implementations follow the same logic: iterate over all diagonal alignments between the two strings and maintain a window that allows exactly one mismatch. Track the last mismatch index and update the number of valid substrings ending at each position. The complexity remains O(n * m) with constant extra space.
How to solve Count Substrings That Differ by One Character in O(n*m)?
Align the two strings along diagonals and iterate through each alignment. Maintain a sliding window that allows exactly one mismatch by storing the last mismatch position. When a second mismatch occurs, shift the window start to maintain the single-mismatch condition. This technique processes each aligned pair once, giving O(n * m) time.
What is the best approach for Count Substrings That Differ by One Character?
The most efficient approach uses diagonal traversal with a sliding window that tracks mismatches between aligned characters of the two strings. For each alignment of s and t, expand a window while recording the last mismatch position. When a second mismatch appears, move the window start forward. This counts valid substrings in O(n * m) time with O(1) extra space.
Is Count Substrings That Differ by One Character asked at Google/Amazon/Meta?
String comparison and substring enumeration problems like this appear frequently in interviews at large tech companies. Variants that involve counting mismatches, sliding windows, or dynamic programming over strings have been reported in interviews at companies such as Amazon, Google, and Meta.
What data structure is used in Count Substrings That Differ by One Character?
The optimized solution mainly relies on string traversal with two-pointer or sliding window logic. No heavy data structures are required; the algorithm tracks mismatch indices while scanning aligned characters. Some explanations frame the idea using dynamic programming concepts for counting valid substring ranges.
What is the time complexity of Count Substrings That Differ by One Character?
The optimized solution runs in O(n * m) time, where n and m are the lengths of the two strings. Each diagonal alignment of the strings is processed once using a sliding window. The brute force substring comparison approach can reach O(n^3) due to repeated character comparisons.