search
HomeBackend DevelopmentPHP TutorialMake String a Subsequence Using Cyclic Increments

Make String a Subsequence Using Cyclic Increments

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:

  1. Consider the indices we will increment separately.
  2. We can maintain two pointers: pointer i for str1 and pointer j for str2, while ensuring they remain within the bounds of the strings.
  3. 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.
  4. 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:

  1. Two Pointers: i and j are initialized to the start of str1 and str2, respectively.
  2. 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].
  3. 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:

  • LinkedIn
  • 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!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Explain how load balancing affects session management and how to address it.Explain how load balancing affects session management and how to address it.Apr 29, 2025 am 12:42 AM

Load balancing affects session management, but can be resolved with session replication, session stickiness, and centralized session storage. 1. Session Replication Copy session data between servers. 2. Session stickiness directs user requests to the same server. 3. Centralized session storage uses independent servers such as Redis to store session data to ensure data sharing.

Explain the concept of session locking.Explain the concept of session locking.Apr 29, 2025 am 12:39 AM

Sessionlockingisatechniqueusedtoensureauser'ssessionremainsexclusivetooneuseratatime.Itiscrucialforpreventingdatacorruptionandsecuritybreachesinmulti-userapplications.Sessionlockingisimplementedusingserver-sidelockingmechanisms,suchasReentrantLockinJ

Are there any alternatives to PHP sessions?Are there any alternatives to PHP sessions?Apr 29, 2025 am 12:36 AM

Alternatives to PHP sessions include Cookies, Token-based Authentication, Database-based Sessions, and Redis/Memcached. 1.Cookies manage sessions by storing data on the client, which is simple but low in security. 2.Token-based Authentication uses tokens to verify users, which is highly secure but requires additional logic. 3.Database-basedSessions stores data in the database, which has good scalability but may affect performance. 4. Redis/Memcached uses distributed cache to improve performance and scalability, but requires additional matching

Define the term 'session hijacking' in the context of PHP.Define the term 'session hijacking' in the context of PHP.Apr 29, 2025 am 12:33 AM

Sessionhijacking refers to an attacker impersonating a user by obtaining the user's sessionID. Prevention methods include: 1) encrypting communication using HTTPS; 2) verifying the source of the sessionID; 3) using a secure sessionID generation algorithm; 4) regularly updating the sessionID.

What is the full form of PHP?What is the full form of PHP?Apr 28, 2025 pm 04:58 PM

The article discusses PHP, detailing its full form, main uses in web development, comparison with Python and Java, and its ease of learning for beginners.

How does PHP handle form data?How does PHP handle form data?Apr 28, 2025 pm 04:57 PM

PHP handles form data using $\_POST and $\_GET superglobals, with security ensured through validation, sanitization, and secure database interactions.

What is the difference between PHP and ASP.NET?What is the difference between PHP and ASP.NET?Apr 28, 2025 pm 04:56 PM

The article compares PHP and ASP.NET, focusing on their suitability for large-scale web applications, performance differences, and security features. Both are viable for large projects, but PHP is open-source and platform-independent, while ASP.NET,

Is PHP a case-sensitive language?Is PHP a case-sensitive language?Apr 28, 2025 pm 04:55 PM

PHP's case sensitivity varies: functions are insensitive, while variables and classes are sensitive. Best practices include consistent naming and using case-insensitive functions for comparisons.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

MantisBT

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.

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools