Given a numeric string S of length N and a digit K, the task is to find the maximum number of distinct strings having a maximum occurrence of K in it formed by replacing any two adjacent digits of S with K if their sum is K.
Examples:
Input: S = “313”, K = 4
Output: 2
Explanation: Possible strings that can be generated are:
- Replacing S[0] and S[1] with K modifies S to “43”.
- Replacing S[1] and S[2] with K modifies S to “34”.
Input: S = “12352”, K = 7
Output: 1
Explanation: Only string possible is by replacing S[3] and S[4] with K i.e., S = “1237”.
Approach: The given problem can be solved using the observation that for some substring of S, there are two types of possibility to contribute to the result i.e., it can be a sequence of “xy” having an equal number of x and y i.e., “xyxy…xyxy” or it can be a sequence of xy having one extra x i.e., “xyxy…xyxyx” where x + y = K.
- Case 1: String of the form “xyxy…xyxy” can be converted to the string “KK…KK” where K occurs (length of substring)/2 times. So, the number of distinct strings that will be formed is 1.
- Case 2: String of the form “xyxy…xyxyx” has one extra ‘x’ and can be converted into the string “KK…KKx” where K occurs (length of substring-1)/2 times. Let this value is M. Upon observation, it can be seen that there will be (M + 1) possible positions for x in the converted string.
Follow the below steps to solve the problem:
- Initialize the variables ans with 1, flag with 0, and start_index with -1 where ans will store the answer up to index i and start_index will be used to store the starting index of each substring from where the desired sequence started.
- Traverse the string S and do the following:
- If the sum of any adjacent digits S[i] and S[i + 1] is K and flag is set to false, set flag to true and start_index to i.
- If flag is true and S[i] and S[i + 1] is not K, set flag to false and also, if (start_index – i + 1) is odd, multiply ans by (start_index – i + 1 – 1)/2 + 1 as stated in Case 2.
- After traversing the string S, if flag is true and (N – start_index) is odd, multiply ans by (N – start_index – 1)/2 + 1.
- After completing the above steps, print ans as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the desired number// of stringsvoid countStrings(string s, int k){ // Store the count of strings int ans = 1; // Store the length of the string int len = s.size(); // Initialize variable to indicate // the start of the substring int flag = 0; // Store the starting index of // the substring int start_ind; // Traverse the string for (int i = 0; i < len - 1; i++) { // If sum of adjacent characters // is K mark the starting index // and set flag to 1 if (s[i] - '0' + s[i + 1] - '0' == k && flag == 0) { flag = 1; start_ind = i; } // If sum of adjacent characters // is not K and the flag variable // is set, end the substring here if (flag == 1 && s[i] - '0' + s[i + 1] - '0' != k) { // Set flag to 0 denoting // the end of substring flag = 0; // Check if the length of the // substring formed is odd if ((i - start_ind + 1) % 2 != 0) // Update the answer ans *= (i - start_ind + 1 - 1) / 2 + 1; } } // If flag is set and end of string // is reached, mark the end of substring if (flag == 1 && (len - start_ind) % 2 != 0) // Update the answer ans *= (len - start_ind) / 2 + 1; // Print the answer cout << ans;}// Driver Codeint main(){ string S = "313"; int K = 4; // Function Call countStrings(S, K);} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to find the desired number// of stringsstatic void countStrings(String s, int k){ // Store the count of strings int ans = 1; // Store the length of the string int len = s.length(); // Initialize variable to indicate // the start of the substring int flag = 0; // Store the starting index of // the substring int start_ind = 0; // Traverse the string for(int i = 0; i < len - 1; i++) { // If sum of adjacent characters // is K mark the starting index // and set flag to 1 if (s.charAt(i) - '0' + s.charAt(i + 1) - '0' == k && flag == 0) { flag = 1; start_ind = i; } // If sum of adjacent characters // is not K and the flag variable // is set, end the substring here if (flag == 1 && s.charAt(i) - '0' + s.charAt(i + 1) - '0' != k) { // Set flag to 0 denoting // the end of substring flag = 0; // Check if the length of the // substring formed is odd if ((i - start_ind + 1) % 2 != 0) // Update the answer ans *= (i - start_ind + 1 - 1) / 2 + 1; } } // If flag is set and end of string // is reached, mark the end of substring if (flag == 1 && (len - start_ind) % 2 != 0) // Update the answer ans *= (len - start_ind) / 2 + 1; // Print the answer System.out.println(ans);} // Driver Codepublic static void main(String[] args){ String S = "313"; int K = 4; // Function Call countStrings(S, K);}}// This code is contributed by jana_sayantan |
Python3
# Python program to implement# the above approach# Function to find the desired number# of stringsdef countStrings(s, k) : # Store the count of strings ans = 1 # Store the length of the string lenn = len(s) # Initialize variable to indicate # the start of the substring flag = 0 # Traverse the string for i in range(lenn - 1): # If sum of adjacent characters # is K mark the starting index # and set flag to 1 if (ord(s[i]) - ord('0') + ord(s[i + 1]) - ord('0') == k and flag == 0) : flag = 1 start_ind = i # If sum of adjacent characters # is not K and the flag variable # is set, end the substring here if (flag == 1 and ord(s[i]) - ord('0') + ord(s[i + 1]) - ord('0') != k) : # Set flag to 0 denoting # the end of substring flag = 0 # Check if the length of the # substring formed is odd if ((i - start_ind + 1) % 2 != 0) : # Update the answer ans *= (i - start_ind + 1 - 1) // 2 + 1 # If flag is set and end of string # is reached, mark the end of substring if (flag == 1 and (lenn - start_ind) % 2 != 0): # Update the answer ans *= (lenn - start_ind) // 2 + 1 # Print the answer print(ans)# Driver CodeS = "313"K = 4 # Function CallcountStrings(S, K)# This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approach using System;class GFG{ // Function to find the desired number// of stringsstatic void countStrings(String s, int k){ // Store the count of strings int ans = 1; // Store the length of the string int len = s.Length; // Initialize variable to indicate // the start of the substring int flag = 0; // Store the starting index of // the substring int start_ind = 0; // Traverse the string for(int i = 0; i < len - 1; i++) { // If sum of adjacent characters // is K mark the starting index // and set flag to 1 if (s[i] - '0' + s[i + 1] - '0' == k && flag == 0) { flag = 1; start_ind = i; } // If sum of adjacent characters // is not K and the flag variable // is set, end the substring here if (flag == 1 && s[i] - '0' + s[i + 1] - '0' != k) { // Set flag to 0 denoting // the end of substring flag = 0; // Check if the length of the // substring formed is odd if ((i - start_ind + 1) % 2 != 0) // Update the answer ans *= (i - start_ind + 1 - 1) / 2 + 1; } } // If flag is set and end of string // is reached, mark the end of substring if (flag == 1 && (len - start_ind) % 2 != 0) // Update the answer ans *= (len - start_ind) / 2 + 1; // Print the answer Console.WriteLine(ans);} // Driver Codepublic static void Main(String[] args){ String S = "313"; int K = 4; // Function Call countStrings(S, K);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to find the desired number// of stringsfunction countStrings(s, k){ // Store the count of strings var ans = 1; // Store the length of the string var len = s.length; // Initialize variable to indicate // the start of the substring var flag = 0; // Store the starting index of // the substring var start_ind; // Traverse the string for (var i = 0; i < len - 1; i++) { // If sum of adjacent characters // is K mark the starting index // and set flag to 1 if ((s[i].charCodeAt(0) - '0'.charCodeAt(0) + s[i + 1].charCodeAt(0) - '0'.charCodeAt(0)) == k && flag == 0) { flag = 1; start_ind = i; } // If sum of adjacent characters // is not K and the flag variable // is set, end the substring here if (flag == 1 && (s[i].charCodeAt(0) - '0'.charCodeAt(0) + s[i + 1].charCodeAt(0) - '0'.charCodeAt(0)) != k) { // Set flag to 0 denoting // the end of substring flag = 0; // Check if the length of the // substring formed is odd if ((i - start_ind + 1) % 2 != 0) // Update the answer ans *= (i - start_ind + 1 - 1) / 2 + 1; } } // If flag is set and end of string // is reached, mark the end of substring if (flag == 1 && (len - start_ind) % 2 != 0) // Update the answer ans *= parseInt((len - start_ind) / 2) + 1; // Print the answer document.write( ans);}// Driver Codevar S = "313";var K = 4;// Function CallcountStrings(S, K);</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
