2825. Make String a Subsequence Using Cyclic Increments
Difficulty: Medium
Topics: Two Pointers, String
You are given two 0-indexed strings str1 and str2.
In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.
Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.
Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.
Example 1:
- Input: str1 = "abc", str2 = "ad"
- Output: true
-
Explanation: Select index 2 in str1.
- Increment str1[2] to become 'd'.
- Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.
Example 2:
- Input: str1 = "zc", str2 = "ad"
- Output: true
-
Explanation: Select indices 0 and 1 in str1.
- Increment str1[0] to become 'a'.
- Increment str1[1] to become 'd'.
- Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.
Example 3:
- Input: str1 = "ab", str2 = "d"
- Output: false
-
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once.
- Therefore, false is returned.
Constraints:
- 1 5
- 1 5
- str1 and str2 consist of only lowercase English letters.
Hint:
- Consider the indices we will increment separately.
- We can maintain two pointers: pointer i for str1 and pointer j for str2, while ensuring they remain within the bounds of the strings.
- If both str1[i] and str2[j] match, or if incrementing str1[i] matches str2[j], we increase both pointers; otherwise, we increment only pointer i.
- It is possible to make str2 a subsequence of str1 if j is at the end of str2, after we can no longer find a match.
Solution:
We need to check if we can make str2 a subsequence of str1 by performing at most one cyclic increment operation on any characters in str1:
Explanation:
- We will use two pointers, i for str1 and j for str2.
- If the character at str1[i] matches str2[j], we move both pointers forward.
- If str1[i] can be incremented to match str2[j] (cyclically), we try to match them and then move both pointers.
- If neither of the above conditions holds, we only move the pointer i for str1.
- Finally, if we can match all characters of str2, then it is possible to make str2 a subsequence of str1, otherwise not.
Let's implement this solution in PHP: 2825. Make String a Subsequence Using Cyclic Increments
<?php /** * @param String $str1 * @param String $str2 * @return Boolean */ function canMakeSubsequence($str1, $str2) { ... ... ... /** * go to ./solution.php */ } // Example Usage $str1 = "abc"; $str2 = "ad"; echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true $str1 = "zc"; $str2 = "ad"; echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true $str1 = "ab"; $str2 = "d"; echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: false ?>
Explanation:
- Two Pointers: i and j are initialized to the start of str1 and str2, respectively.
-
Matching Logic: Inside the loop, we check if the characters at str1[i] and str2[j] are the same or if we can increment str1[i] to match str2[j] cyclically.
- The cyclic increment condition is handled using (ord($str1[$i]) 1 - ord('a')) % 26 which checks if str1[i] can be incremented to match str2[j].
- Subsequence Check: If we have iterated through str2 completely (i.e., j == m), it means str2 is a subsequence of str1. Otherwise, it's not.
Time Complexity:
- The algorithm iterates through str1 once, and each character in str2 is checked only once, so the time complexity is O(n), where n is the length of str1.
Space Complexity:
- The space complexity is O(1) since we only use a few pointers and do not need extra space dependent on the input size.
This solution efficiently checks if it's possible to make str2 a subsequence of str1 with at most one cyclic increment operation.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
- GitHub
The above is the detailed content of Make String a Subsequence Using Cyclic Increments. For more information, please follow other related articles on the PHP Chinese website!

PHP remains important in modern web development, especially in content management and e-commerce platforms. 1) PHP has a rich ecosystem and strong framework support, such as Laravel and Symfony. 2) Performance optimization can be achieved through OPcache and Nginx. 3) PHP8.0 introduces JIT compiler to improve performance. 4) Cloud-native applications are deployed through Docker and Kubernetes to improve flexibility and scalability.

PHP is suitable for web development, especially in rapid development and processing dynamic content, but is not good at data science and enterprise-level applications. Compared with Python, PHP has more advantages in web development, but is not as good as Python in the field of data science; compared with Java, PHP performs worse in enterprise-level applications, but is more flexible in web development; compared with JavaScript, PHP is more concise in back-end development, but is not as good as JavaScript in front-end development.

PHP and Python each have their own advantages and are suitable for different scenarios. 1.PHP is suitable for web development and provides built-in web servers and rich function libraries. 2. Python is suitable for data science and machine learning, with concise syntax and a powerful standard library. When choosing, it should be decided based on project requirements.

PHP is a scripting language widely used on the server side, especially suitable for web development. 1.PHP can embed HTML, process HTTP requests and responses, and supports a variety of databases. 2.PHP is used to generate dynamic web content, process form data, access databases, etc., with strong community support and open source resources. 3. PHP is an interpreted language, and the execution process includes lexical analysis, grammatical analysis, compilation and execution. 4.PHP can be combined with MySQL for advanced applications such as user registration systems. 5. When debugging PHP, you can use functions such as error_reporting() and var_dump(). 6. Optimize PHP code to use caching mechanisms, optimize database queries and use built-in functions. 7

The reasons why PHP is the preferred technology stack for many websites include its ease of use, strong community support, and widespread use. 1) Easy to learn and use, suitable for beginners. 2) Have a huge developer community and rich resources. 3) Widely used in WordPress, Drupal and other platforms. 4) Integrate tightly with web servers to simplify development deployment.

PHP remains a powerful and widely used tool in modern programming, especially in the field of web development. 1) PHP is easy to use and seamlessly integrated with databases, and is the first choice for many developers. 2) It supports dynamic content generation and object-oriented programming, suitable for quickly creating and maintaining websites. 3) PHP's performance can be improved by caching and optimizing database queries, and its extensive community and rich ecosystem make it still important in today's technology stack.

In PHP, weak references are implemented through the WeakReference class and will not prevent the garbage collector from reclaiming objects. Weak references are suitable for scenarios such as caching systems and event listeners. It should be noted that it cannot guarantee the survival of objects and that garbage collection may be delayed.

The \_\_invoke method allows objects to be called like functions. 1. Define the \_\_invoke method so that the object can be called. 2. When using the $obj(...) syntax, PHP will execute the \_\_invoke method. 3. Suitable for scenarios such as logging and calculator, improving code flexibility and readability.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Zend Studio 13.0.1
Powerful PHP integrated development environment

SublimeText3 Linux new version
SublimeText3 Linux latest version

DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Notepad++7.3.1
Easy-to-use and free code editor

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.