string-matching

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3529 - Count Cells in Overlapping Horizontal and Vertical Substrings

LeetCode Problem 3529 Difficulty: 🟡 Medium Topics: Array, String, Rolling Hash, String Matching, Matrix, Hash Function Solution Problem Understanding We are given a character matrix and a pattern string. The key observation is that the problem defines two unusual traversal orders: A horizontal traversal reads the matrix row by row, from left to right. When a row ends, reading continues at the beginning of the next row. A vertical traversal...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3474 - Lexicographically Smallest Generated String

LeetCode Problem 3474 Difficulty: 🔴 Hard Topics: String, Greedy, String Matching Solution LeetCode 3474 - Lexicographically Smallest Generated String Problem Understanding We are given two strings: str1 of length n , containing only 'T' and 'F' str2 of length m , containing lowercase English letters We must construct a string word of length n + m - 1 . For every position i in str1 , the substring of word...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3407 - Substring Matching Pattern

LeetCode Problem 3407 Difficulty: 🟢 Easy Topics: String, String Matching Solution LeetCode 3407. Substring Matching Pattern Problem Understanding The problem gives us two strings: s , the source string. p , a pattern string containing exactly one '*' . The special character '*' can represent any sequence of characters, including an empty sequence. The goal is to determine whether there exists some substring of s that can match the pattern...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3455 - Shortest Matching Substring

LeetCode Problem 3455 Difficulty: 🔴 Hard Topics: Two Pointers, String, Binary Search, String Matching Solution Problem Understanding This problem asks us to find the length of the shortest substring in a string s that matches a pattern p , where p contains exactly two '*' wildcards . Each '*' can match zero or more characters. The substring of s must contain all the letters in p in the correct order,...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3291 - Minimum Number of Valid Strings to Form Target I

LeetCode Problem 3291 Difficulty: 🟡 Medium Topics: Array, String, Binary Search, Dynamic Programming, Greedy, Trie, Segment Tree, Rolling Hash, String Matching, Hash Function Solution Problem Understanding We are given a list of strings called words and another string called target . The task is to construct target by concatenating several smaller strings, where each smaller string must be a prefix of at least one word in words . A prefix...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3303 - Find the Occurrence of First Almost Equal Substring

LeetCode Problem 3303 Difficulty: 🔴 Hard Topics: String, String Matching Solution Problem Understanding We are given two strings, s and pattern . The task is to find the smallest starting index in s such that the substring of length len(pattern) is "almost equal" to pattern . Two strings are considered almost equal if we can modify at most one character in one string to make the two strings identical. That...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2185 - Counting Words With a Given Prefix

LeetCode Problem 2185 Difficulty: 🟢 Easy Topics: Array, String, String Matching Solution Problem Understanding The problem gives us two inputs: An array of strings called words A string called pref We must count how many strings inside words start with the string pref . A prefix means the beginning portion of a string. For example: "at" is a prefix of "attention" "pay" is a prefix of "pay" "code" is not...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2430 - Maximum Deletions on a String

LeetCode Problem 2430 Difficulty: 🔴 Hard Topics: String, Dynamic Programming, Rolling Hash, String Matching, Hash Function Solution Maximum Deletions on a String Problem Understanding The problem gives us a string s consisting only of lowercase English letters. We want to completely delete the string using the maximum possible number of operations. In a single operation, we have two possible actions: Delete the entire remaining string immediately. Delete only the first...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3006 - Find Beautiful Indices in the Given Array I

LeetCode Problem 3006 Difficulty: 🟡 Medium Topics: Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem gives us a string s and two smaller strings, a and b . We need to find every index i where substring a appears in s , but only if there exists at least one occurrence of substring b close enough to it. More formally, an index...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3023 - Find Pattern in Infinite Stream I

LeetCode Problem 3023 Difficulty: 🟡 Medium Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function Solution Problem Understanding The problem asks us to detect the first occurrence of a given binary pattern within an infinite stream of bits. We are given an object stream that allows us to read one bit at a time using the next() function. Our task is to return the 0-based index in the...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2301 - Match Substring After Replacement

LeetCode Problem 2301 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, String Matching Solution Problem Understanding The problem gives us a string s , a target string sub , and a list of character replacement rules called mappings . Each mapping [old, new] means that a character old inside sub may be replaced with new . The replacement is optional, and every character in sub can be replaced at most...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3029 - Minimum Time to Revert Word to Initial State I

LeetCode Problem 3029 Difficulty: 🟡 Medium Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem gives us a string word and an integer k . Every second, we are forced to perform two operations in sequence: Remove the first k characters from the string. Append any k characters to the end of the string. The appended characters are completely under our control. They do not need...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3292 - Minimum Number of Valid Strings to Form Target II

LeetCode Problem 3292 Difficulty: 🔴 Hard Topics: Array, String, Binary Search, Dynamic Programming, Greedy, Segment Tree, Rolling Hash, String Matching, Hash Function Solution LeetCode 3292 - Minimum Number of Valid Strings to Form Target II Problem Understanding We are given a collection of strings words and a target string target . A string is considered valid if it is a prefix of at least one word in words . This...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3045 - Count Prefix and Suffix Pairs II

LeetCode Problem 3045 Difficulty: 🔴 Hard Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to count the number of ordered pairs (i, j) in a list of strings words such that i < j and words[i] is both a prefix and a suffix of words[j] . In other words, for a pair to be valid, the smaller-indexed string must appear at...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3008 - Find Beautiful Indices in the Given Array II

LeetCode Problem 3008 Difficulty: 🔴 Hard Topics: Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function Solution LeetCode 3008 - Find Beautiful Indices in the Given Array II Problem Understanding This problem asks us to find every starting index where the substring a appears inside the string s , subject to an additional proximity condition involving another substring b . More specifically, an index i is considered beautiful...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3034 - Number of Subarrays That Match a Pattern I

LeetCode Problem 3034 Difficulty: 🟡 Medium Topics: Array, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to count how many contiguous subarrays of nums match a given relationship pattern . Instead of comparing exact values, the pattern describes how adjacent numbers should relate to each other. Each value in pattern represents a comparison between two consecutive elements in a subarray: 1 means the next number...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3042 - Count Prefix and Suffix Pairs I

LeetCode Problem 3042 Difficulty: 🟢 Easy Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function Solution LeetCode 3042 - Count Prefix and Suffix Pairs I Problem Understanding The problem gives us an array of strings called words . For every pair of indices (i, j) where i < j , we must determine whether words[i] is both a prefix and a suffix of words[j] . A string is a...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3031 - Minimum Time to Revert Word to Initial State II

LeetCode Problem 3031 Difficulty: 🔴 Hard Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem requires simulating a repetitive transformation on a string word where, at each second, the first k characters are removed, and then any k characters are appended to the end. The key challenge is to determine the minimum number of seconds required for the string to return exactly to its initial state....

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2223 - Sum of Scores of Built Strings

LeetCode Problem 2223 Difficulty: 🔴 Hard Topics: String, Binary Search, Rolling Hash, Suffix Array, String Matching, Hash Function Solution Problem Understanding The problem gives us a final string s and describes a process where the string is built by repeatedly prepending characters to the front. This means that every intermediate string si is actually a suffix of the final string s . For example, if: s = "abaca" Then: s1...

Practice › LeetCode › LeetCode 28xx ›

LeetCode 2851 - String Transformation

LeetCode Problem 2851 Difficulty: 🔴 Hard Topics: Math, String, Dynamic Programming, String Matching Solution Problem Understanding The problem asks us to transform a string s into a target string t using a very specific operation: choosing a non-empty suffix of s (not the whole string) and moving it to the front. The operation can be repeated exactly k times, and we are asked to count the number of distinct sequences...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3037 - Find Pattern in Infinite Stream II

LeetCode Problem 3037 Difficulty: 🔴 Hard Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function Solution Problem Understanding The problem requires us to detect the first occurrence of a binary pattern within a theoretically infinite stream of bits. The stream is accessed sequentially using the next() method, which returns one bit at a time. Our task is to determine the index in the stream where the given pattern...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3036 - Number of Subarrays That Match a Pattern II

LeetCode Problem 3036 Difficulty: 🔴 Hard Topics: Array, Rolling Hash, String Matching, Hash Function Solution This guide will be very long, likely exceeding a single message cleanly while still maintaining the level of detail and formatting quality you requested for a reference document. I can provide the complete guide in full , including: Problem Understanding Approaches (Brute Force + Optimal KMP) Algorithm Walkthrough Python Solution Go Solution Worked Examples (step-by-step...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 28 - Find the Index of the First Occurrence in a String

LeetCode Problem 28 Difficulty: 🟢 Easy Topics: Two Pointers, String, String Matching Solution Problem Understanding This problem asks us to locate the first occurrence of one string inside another string. The string we are searching for is called needle , and the larger string we search inside is called haystack . More formally, we need to determine whether needle appears as a contiguous substring inside haystack . If it does,...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 758 - Bold Words in String

LeetCode Problem 758 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, String Matching Solution Problem Understanding The problem gives us two inputs: an array of strings called words , and a target string s . Every occurrence of every word from words inside s must become bold by surrounding that substring with <b> and </b> tags. The important requirement is that we must use the minimum number of tags...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1408 - String Matching in an Array

LeetCode Problem 1408 Difficulty: 🟢 Easy Topics: Array, String, String Matching Solution You included two different problems in one message, and the second problem (LeetCode 1408) appears to replace the first one while repeating the formatting instructions. I will proceed with LeetCode 1408 - String Matching in an Array . Problem Understanding The problem gives us an array of unique strings called words . We need to find every string...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1455 - Check If a Word Occurs As a Prefix of Any Word in a Sentence

LeetCode Problem 1455 Difficulty: 🟢 Easy Topics: Two Pointers, String, String Matching Solution Problem Understanding The problem asks us to determine whether a given searchWord occurs as a prefix of any word within a sentence. A sentence is defined as a string of lowercase English letters separated by single spaces, and a prefix is any contiguous leading substring of a word. We are asked to return the 1-indexed position of...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 686 - Repeated String Match

LeetCode Problem 686 Difficulty: 🟡 Medium Topics: String, String Matching Solution Problem Understanding The problem asks us to determine the minimum number of times a string a must be repeated such that another string b becomes a substring of the repeated version of a . A substring is a consecutive sequence of characters within a string. The input consists of two strings, a and b , both of length between...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1668 - Maximum Repeating Substring

LeetCode Problem 1668 Difficulty: 🟢 Easy Topics: String, Dynamic Programming, String Matching Solution Problem Understanding This problem asks us to determine how many times a given string word can be repeated consecutively while still appearing as a substring inside another string called sequence . More formally, a string is considered k-repeating if word concatenated k times appears somewhere inside sequence as a contiguous substring. Our goal is to find the...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 214 - Shortest Palindrome

LeetCode Problem 214 Difficulty: 🔴 Hard Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem gives a string s and asks us to create the shortest possible palindrome by adding characters only at the beginning of the string. A palindrome is a string that reads the same forward and backward. The key restriction is that we are not allowed to insert characters in the middle or...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1023 - Camelcase Matching

LeetCode Problem 1023 Difficulty: 🟡 Medium Topics: Array, Two Pointers, String, Trie, String Matching Solution Problem Understanding The problem gives us a list of query strings and a target camel case pattern. For each query, we must determine whether the query can be formed by inserting only lowercase English letters into the pattern. The important restriction is that we are only allowed to insert lowercase letters. We are not allowed...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1764 - Form Array by Concatenating Subarrays of Another Array

LeetCode Problem 1764 Difficulty: 🟡 Medium Topics: Array, Two Pointers, Greedy, String Matching Solution Problem Understanding The problem asks us to determine whether we can select disjoint subarrays from a given array nums such that each subarray matches exactly one of the subarrays in the groups array, in order. A subarray is contiguous, and "disjoint" means no element in nums is part of more than one selected subarray. The order...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 459 - Repeated Substring Pattern

LeetCode Problem 459 Difficulty: 🟢 Easy Topics: String, String Matching Solution Problem Understanding The problem asks us to determine whether a given string can be formed by repeating one of its substrings multiple times. In other words, we want to know if there exists some substring pattern such that concatenating that pattern repeatedly recreates the entire string exactly. For example, consider the string "abab" : The substring "ab" repeated twice...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1397 - Find All Good Strings

LeetCode Problem 1397 Difficulty: 🔴 Hard Topics: String, Dynamic Programming, String Matching Solution Problem Understanding The problem asks us to count how many strings of length n satisfy three conditions simultaneously: The string must be lexicographically greater than or equal to s1 The string must be lexicographically less than or equal to s2 The string must not contain evil as a substring anywhere The result can become extremely large, so...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 572 - Subtree of Another Tree

LeetCode Problem 572 Difficulty: 🟢 Easy Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function Solution LeetCode 572 - Subtree of Another Tree Problem Understanding This problem asks us to determine whether one binary tree appears as an exact subtree inside another binary tree. We are given two binary trees: root , the main tree subRoot , the candidate subtree We must return true if there exists some node...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 796 - Rotate String

LeetCode Problem 796 Difficulty: 🟢 Easy Topics: String, String Matching Solution Problem Understanding The problem asks us to determine whether one string can be transformed into another string using repeated left rotations. A single shift operation removes the first character of the string and appends it to the end. For example: "abcde" becomes "bcdea" after one shift "bcdea" becomes "cdeab" after another shift We are given two strings, s and...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 616 - Add Bold Tag in String

LeetCode Problem 616 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, String Matching Solution Problem Understanding The problem asks us to insert HTML-style bold tags into a string whenever a substring matches any word from a given dictionary of words. We are given: A string s An array words , where each element is a pattern we want to highlight For every occurrence of every word inside s ,...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1392 - Longest Happy Prefix

LeetCode Problem 1392 Difficulty: 🔴 Hard Topics: String, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to find the longest substring that is both a prefix and a suffix of the given string s , while also ensuring that the substring is not equal to the entire string itself. A prefix is a substring that starts at index 0 , while a suffix is a...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1032: Stream of Characters

Problem Restatement We implement a StreamChecker class: StreamChecker(words) : Initialize with a list of words. query(letter) : Add the letter to the stream. Return true if any word in words is a suffix of the letters queried so far. The official constraints state that 1 <= words.length <= 2000 , 1 <= words[i].length <= 2000 , and up to 4 * 10^4 calls to query . Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 796: Rotate String

Problem Restatement We are given two strings: s goal A shift on s means moving the leftmost character to the rightmost position. For example: abcde -> bcdea We need to return True if s can become goal after some number of shifts. Otherwise, return False . Zero shifts are allowed, so if s == goal , the answer is True . Input and Output Item Meaning Input Two strings s...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 686: Repeated String Match

Problem Restatement We are given two strings a and b . We need to repeat string a some number of times so that b becomes a substring of the repeated string. Return the minimum number of repetitions needed. If it is impossible, return -1 . For example: a = "abcd" b = "cdabcdab" Repeating a two times gives: abcdabcd b is not a substring. Repeating a three times gives: abcdabcdabcd...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 616: Add Bold Tag in String

Problem Restatement We are given a string s and an array of strings words . We need to wrap every substring of s that appears in words with a pair of bold tags: <b>...</b> If two matching substrings overlap, they should be wrapped together with one pair of tags. If two matching substrings are adjacent, they should also be combined into one bold region. Return the final string after inserting...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 459: Repeated Substring Pattern

Problem Restatement We are given a string s . We need to check whether s can be constructed by taking a non-empty substring and repeating it multiple times. The substring must be shorter than the whole string, because repeating the entire string once does not count. The official problem asks whether s can be built by appending multiple copies of a substring together. For example: s = "abab" This can...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 28: Find the Index of the First Occurrence in a String

Problem Restatement We are given two strings: haystack and needle . We need to return the index where needle first appears inside haystack . If needle does not appear inside haystack , return -1 . For this current version of the problem, both strings have length at least 1 , and both contain only lowercase English letters. Input and Output Item Meaning Input Two strings: haystack and needle Output The...

#string-matching

LeetCode 3529 - Count Cells in Overlapping Horizontal and Vertical Substrings

LeetCode 3474 - Lexicographically Smallest Generated String

LeetCode 3407 - Substring Matching Pattern

LeetCode 3455 - Shortest Matching Substring

LeetCode 3291 - Minimum Number of Valid Strings to Form Target I

LeetCode 3303 - Find the Occurrence of First Almost Equal Substring

LeetCode 2185 - Counting Words With a Given Prefix

LeetCode 2430 - Maximum Deletions on a String

LeetCode 3006 - Find Beautiful Indices in the Given Array I

LeetCode 3023 - Find Pattern in Infinite Stream I

LeetCode 2301 - Match Substring After Replacement

LeetCode 3029 - Minimum Time to Revert Word to Initial State I

LeetCode 3292 - Minimum Number of Valid Strings to Form Target II

LeetCode 3045 - Count Prefix and Suffix Pairs II

LeetCode 3008 - Find Beautiful Indices in the Given Array II

LeetCode 3034 - Number of Subarrays That Match a Pattern I

LeetCode 3042 - Count Prefix and Suffix Pairs I

LeetCode 3031 - Minimum Time to Revert Word to Initial State II

LeetCode 2223 - Sum of Scores of Built Strings

LeetCode 2851 - String Transformation

LeetCode 3037 - Find Pattern in Infinite Stream II

LeetCode 3036 - Number of Subarrays That Match a Pattern II

LeetCode 28 - Find the Index of the First Occurrence in a String

LeetCode 758 - Bold Words in String

LeetCode 1408 - String Matching in an Array

LeetCode 1455 - Check If a Word Occurs As a Prefix of Any Word in a Sentence

LeetCode 686 - Repeated String Match

LeetCode 1668 - Maximum Repeating Substring

LeetCode 214 - Shortest Palindrome

LeetCode 1023 - Camelcase Matching

LeetCode 1764 - Form Array by Concatenating Subarrays of Another Array

LeetCode 459 - Repeated Substring Pattern

LeetCode 1397 - Find All Good Strings

LeetCode 572 - Subtree of Another Tree

LeetCode 796 - Rotate String

LeetCode 616 - Add Bold Tag in String

LeetCode 1392 - Longest Happy Prefix

LeetCode 1032: Stream of Characters

LeetCode 796: Rotate String

LeetCode 686: Repeated String Match

LeetCode 616: Add Bold Tag in String

LeetCode 459: Repeated Substring Pattern

LeetCode 28: Find the Index of the First Occurrence in a String