Find longest substring of S1 that matches in S2 with a given cost
Given two strings S1 and S2 of length n. Additionally, two positive integers, target and C. The task is to determine the maximum length of a contiguous substring in S1 such that, by changing any character in the substring of S1 to another character, the resulting substring matches the corresponding segment in S2, and the total cost of these changes is at most target, where the cost of transformation for each character is C units.
Note: If there are multiple valid substrings with the same maximum length, provide any one of them as the answer.
Examples:
Input: S1 = “abcd”, S2 = “bcdf”, C = 1, target = 3
Output: 1 3
Explanation: Substring of S1 from index 1 to 3 is “bcd” that can change to “cdf”. The cost of changing would be 3. So the maximum length is 3.Input: S1 = “adcd”, S2 = “cdef”, C = 2, target = 5
Output: 1 3
Approach:
The idea is to use Binary Search on Answer method to find what can be the maximum possible length. For each potential length (from the midpoint of the current search range [start, end]), use a sliding window approach to check all substrings of that length (i.e, mid) in S1. Calculates the transformation cost for each substring and checks if it’s less than or equal to the target. If a valid substring is found, the starting and ending positions are updated, and the search continues with larger lengths. If no valid substring is found for a certain length, the search continues with smaller lengths.
Steps-by-step approach:
- Initialize a variable start with the minimum valid length substring possible i.e., 0.
- Initialize a variable end with the maximum valid length substring possible i.e., the size of the string itself.
- Initialize a variable result for storing the maximum length of valid substring
- While the start is less than the end, do the following:
- Calculate the mid = (start + end) /2
- Check if mid is the possible length for a valid substring
- Assign the result to mid
- Shift start to mid + 1.
- Otherwise, shift end to mid.
- If any valid substring is possible then print the starting index and the ending index of the valid substring.
Below is the impelementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Initilise S1 variable startPos and endPos // for storing the starting and ending // position of valid substring // respectively. int startPos = -1, endPos = -1; bool isValid( int len, string& S1, string& S2, int C, int target) { int i = 0, j = 0, n = S1.size(), cost = 0; // Initilise S1 variable flag to false. // It will keep track of any valid // substring of length len is // possible or not bool flag = false ; while (j < n) { // Include the cost required to // convert S1[j] to S2[j] cost += ((S1[j] != S2[j]) ? C : 0); // If window size is equal to len // then shift the window. if (j - i + 1 == len) { // Check if any valid substring // then keep the indices of // valid substring in startPos // and endPos if (cost <= target) { flag = true ; startPos = i; endPos = j; } // Remove the calculation of // ith indices as our window // we have to slide our window cost -= ((S1[j] != S2[j]) ? C : 0); i++; } j++; } // Return the flag return flag; } void validSubstring(string S1, string S2, int C, int target) { startPos = -1, endPos = -1; // Initilise S1 variable start with // minimum valid length // substring possible. int start = 0; // Initilise S1 variable end with // maximum valid length substring // possible. int end = S1.size(); int n = S1.size(); // Initilise S1 variable result for // storing the maximum length of // valid substring int result = 0; // Do while start is less // than equal to end while (start < end) { // Calculate the mid int mid = (start + end) / 2; // Check if mid is possible length // for valid substring if (isValid(mid, S1, S2, C, target)) { // Assign result to mid result = mid; // Shift start to mid + 1 start = mid + 1; } // Otherwise shift end to mid - 1 else { end = mid; } } if (startPos == -1) cout << "Not possible\n" ; else cout << startPos << " " << endPos << "\n" ; } // Driver code int main() { // First test case string S1 = "abcd" , S2 = "bcdf" ; int C = 1, target = 5; validSubstring(S1, S2, C, target); // Second test case S1 = "abc" , S2 = "cdf" ; C = 10, target = 3; validSubstring(S1, S2, C, target); // Third test case S1 = "abcb" , S2 = "cdfb" ; C = 2, target = 2; validSubstring(S1, S2, C, target); return 0; } |
Java
import java.util.*; public class Main { // Initialize variables to store the starting and ending positions of a valid substring. static int startPos = - 1 , endPos = - 1 ; // Check if a substring of a given length is a valid substring with cost less than or equal to the target. static boolean isValid( int len, String S1, String S2, int C, int target) { int i = 0 , j = 0 , n = S1.length(), cost = 0 ; boolean flag = false ; // Iterate through the strings to check validity of the substring. while (j < n) { // Include the cost required to convert S1[j] to S2[j]. cost += (S1.charAt(j) != S2.charAt(j)) ? C : 0 ; // If the window size is equal to len, then shift the window. if (j - i + 1 == len) { // Check if any valid substring and keep the indices of the valid substring in startPos and endPos. if (cost <= target) { flag = true ; startPos = i; endPos = j; } // Remove the calculation of ith indices as the window is sliding. cost -= (S1.charAt(i) != S2.charAt(i)) ? C : 0 ; i++; } j++; } // Return the flag indicating if a valid substring was found. return flag; } // Find the maximum length of a valid substring and its starting and ending positions. static void validSubstring(String S1, String S2, int C, int target) { startPos = - 1 ; endPos = - 1 ; int start = 0 ; int end = S1.length(); int n = S1.length(); int result = 0 ; // Perform binary search to find the maximum length of a valid substring. while (start < end) { int mid = (start + end) / 2 ; // Check if mid is a possible length for a valid substring. if (isValid(mid, S1, S2, C, target)) { // Assign result to mid and shift start to mid + 1. result = mid; start = mid + 1 ; } else { // Otherwise, shift end to mid - 1. end = mid; } } // If no valid substring is found, print "Not possible"; otherwise, print the starting and ending positions. if (startPos == - 1 ) System.out.println( "Not possible" ); else System.out.println(startPos + " " + endPos); } // Driver code public static void main(String[] args) { // First test case String S1 = "abcd" , S2 = "bcdf" ; int C = 1 , target = 5 ; validSubstring(S1, S2, C, target); // Second test case S1 = "abc" ; S2 = "cdf" ; C = 10 ; target = 3 ; validSubstring(S1, S2, C, target); // Third test case S1 = "abcb" ; S2 = "cdfb" ; C = 2 ; target = 2 ; validSubstring(S1, S2, C, target); } } // This code is contributed by shivamgupta0987654321 |
C#
using System; class Program { // Initialize startPos and endPos to store the starting // and ending position of the valid substring static int startPos = -1, endPos = -1; // Function to check if a valid substring of length // 'len' exists static bool IsValid( int len, string S1, string S2, int C, int target) { int i = 0, j = 0, n = S1.Length, cost = 0; bool flag = false ; while (j < n) { // Include the cost required to convert S1[j] to // S2[j] cost += (S1[j] != S2[j]) ? C : 0; // If window size is equal to len, then check if // it's a valid substring if (j - i + 1 == len) { if (cost <= target) { flag = true ; startPos = i; endPos = j; } // Remove the cost of the ith index as the // window slides cost -= (S1[i] != S2[i]) ? C : 0; i++; } j++; } return flag; } // Function to find the maximum length of a valid // substring static void ValidSubstring( string S1, string S2, int C, int target) { startPos = -1; endPos = -1; int start = 0; int end = S1.Length; while (start < end) { int mid = (start + end) / 2; // Check if mid is a possible length for a valid // substring if (IsValid(mid, S1, S2, C, target)) { // Shift start to mid + 1 start = mid + 1; } else { // Otherwise shift end to mid end = mid; } } if (startPos == -1) Console.WriteLine( "Not possible" ); else Console.WriteLine(startPos + " " + endPos); } // Driver code static void Main( string [] args) { // First test case string S1 = "abcd" , S2 = "bcdf" ; int C = 1, target = 5; ValidSubstring(S1, S2, C, target); // Second test case S1 = "abc" ; S2 = "cdf" ; C = 10; target = 3; ValidSubstring(S1, S2, C, target); // Third test case S1 = "abcb" ; S2 = "cdfb" ; C = 2; target = 2; ValidSubstring(S1, S2, C, target); } } |
Javascript
// Initialize startPos and endPos for storing the starting and ending position of a valid substring respectively let startPos = -1, endPos = -1; // Function to check if a substring of length 'len' is a valid substring function isValid(len, S1, S2, C, target) { let i = 0, j = 0, n = S1.length, cost = 0; let flag = false ; while (j < n) { // Include the cost required to convert S1[j] to S2[j] cost += (S1[j] !== S2[j] ? C : 0); // If the window size is equal to len, check if it's a valid substring if (j - i + 1 === len) { if (cost <= target) { flag = true ; startPos = i; endPos = j; } // Remove the calculation of ith indices as we slide the window cost -= (S1[j] !== S2[j] ? C : 0); i++; } j++; } return flag; } // Function to find the maximum length of a valid substring function validSubstring(S1, S2, C, target) { startPos = -1; endPos = -1; let start = 0; let end = S1.length; let result = 0; while (start < end) { let mid = Math.floor((start + end) / 2); // Check if mid is a possible length for a valid substring if (isValid(mid, S1, S2, C, target)) { result = mid; start = mid + 1; } else { end = mid; } } // Output the result if (startPos === -1) console.log( "Not possible" ); else console.log(startPos + " " + endPos); } // First test case let S1 = "abcd" , S2 = "bcdf" ; let C = 1, target = 5; validSubstring(S1, S2, C, target); // Second test case S1 = "abc" , S2 = "cdf" ; C = 10, target = 3; validSubstring(S1, S2, C, target); // Third test case S1 = "abcb" , S2 = "cdfb" ; C = 2, target = 2; validSubstring(S1, S2, C, target); |
Python3
def is_valid(length, S1, S2, C, target): i, j, n, cost = 0 , 0 , len (S1), 0 flag = False start_pos, end_pos = - 1 , - 1 # Initialize start_pos and end_pos while j < n: # Include the cost required to convert S1[j] to S2[j] cost + = (C if S1[j] ! = S2[j] else 0 ) # If window size is equal to length, then shift the window if j - i + 1 = = length: # Check if any valid substring, then keep the indices of valid substring in start_pos and end_pos if cost < = target: flag = True start_pos, end_pos = i, j # Remove the calculation of ith indices as our window, we have to slide our window cost - = (C if S1[j] ! = S2[j] else 0 ) i + = 1 j + = 1 return flag, start_pos, end_pos def valid_substring(S1, S2, C, target): start_pos, end_pos = - 1 , - 1 start, end, n = 0 , len (S1), len (S1) result = 0 while start < end: mid = (start + end) / / 2 # Check if mid is a possible length for a valid substring is_valid_flag, i, j = is_valid(mid, S1, S2, C, target) if is_valid_flag: # Assign result to mid, shift start to mid + 1 result = mid start = mid + 1 start_pos, end_pos = i, j else : # Otherwise, shift end to mid end = mid if start_pos = = - 1 : print ( "Not possible" ) else : print (start_pos, end_pos) # First test case S1, S2 = "abcd" , "bcdf" C, target = 1 , 5 valid_substring(S1, S2, C, target) # Second test case S1, S2 = "abc" , "cdf" C, target = 10 , 3 valid_substring(S1, S2, C, target) # Third test case S1, S2 = "abcb" , "cdfb" C, target = 2 , 2 valid_substring(S1, S2, C, target) |
1 3 Not possible 2 3
Time Complexity: O(N* log(N))
Auxiliary Space: O(1)