Sub-strings that start and end with one character and have at least one other
Given the string str which contains only the characters x and y, the task is to count all the sub-strings that start and end with an x and have at least a single y.
Examples:
Input: str = “xyyxx”
Output: 2
“xyyx” and “xyyxx” are the only valid sub-strings.Input: str = “xyy”
Output: 0
Approach:
- Create an array countX[] where countX[i] stores the total x from i to n – 1.
- Now, for every x in the string, find the first y that appears after this x.
- And update count = count + countX[indexOf(y)] because, with this x as the starting index, all sub-strings will be valid that will end at any x after they find y.
- Return the count in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function that returns the index of next occurrence // of the character c in string str starting from index start int nextIndex(string str, int start, char c) { // Starting from start for ( int i = start; i < str.length(); i++) { // If current character = c if (str[i] == c) return i; } // Not found return -1; } // Function to return the count of required sub-strings int countSubStrings(string str) { int i, n = str.length(); // Stores running count of 'x' starting from the end int countX[n]; int count = 0; for (i = n - 1; i >= 0; i--) { if (str[i] == 'x' ) count++; countX[i] = count; } // Next index of 'x' starting from index 0 int nextIndexX = nextIndex(str, 0, 'x' ); // Next index of 'y' starting from index 0 int nextIndexY = nextIndex(str, 0, 'y' ); // To store the count of required sub-strings count = 0; while (nextIndexX != -1 && nextIndexY != -1) { // If 'y' appears before 'x' // it won't contribute to a valid sub-string if (nextIndexX > nextIndexY) { // Find next occurrence of 'y' nextIndexY = nextIndex(str, nextIndexY + 1, 'y' ); continue ; } // If 'y' appears after 'x' // every sub-string ending at an 'x' appearing after this 'y' // and starting with the current 'x' is a valid sub-string else { count += countX[nextIndexY]; // Find next occurrence of 'x' nextIndexX = nextIndex(str, nextIndexX + 1, 'x' ); } } // Return the count return count; } // Driver code int main() { string s = "xyyxx" ; cout << countSubStrings(s); } // This code is contributed by ihritik |
Java
// Java implementation of the approach public class GFG { // Function that returns the index of next occurrence // of the character c in string str starting from index start static int nextIndex(String str, int start, char c) { // Starting from start for ( int i = start; i < str.length(); i++) { // If current character = c if (str.charAt(i) == c) return i; } // Not found return - 1 ; } // Function to return the count of required sub-strings static int countSubStrings(String str) { int i, n = str.length(); // Stores running count of 'x' starting from the end int countX[] = new int [n]; int count = 0 ; for (i = n - 1 ; i >= 0 ; i--) { if (str.charAt(i) == 'x' ) count++; countX[i] = count; } // Next index of 'x' starting from index 0 int nextIndexX = nextIndex(str, 0 , 'x' ); // Next index of 'y' starting from index 0 int nextIndexY = nextIndex(str, 0 , 'y' ); // To store the count of required sub-strings count = 0 ; while (nextIndexX != - 1 && nextIndexY != - 1 ) { // If 'y' appears before 'x' // it won't contribute to a valid sub-string if (nextIndexX > nextIndexY) { // Find next occurrence of 'y' nextIndexY = nextIndex(str, nextIndexY + 1 , 'y' ); continue ; } // If 'y' appears after 'x' // every sub-string ending at an 'x' appearing after this 'y' // and starting with the current 'x' is a valid sub-string else { count += countX[nextIndexY]; // Find next occurrence of 'x' nextIndexX = nextIndex(str, nextIndexX + 1 , 'x' ); } } // Return the count return count; } // Driver code public static void main(String[] args) { String s = "xyyxx" ; System.out.println(countSubStrings(s)); } } |
Python3
# Python3 implementation of the approach # Function that returns the index of next occurrence # of the character c in string str starting from index start def nextIndex( str , start, c): # Starting from start for i in range (start, len ( str )): # If current character = c if ( str [i] = = c): return i; # Not found return - 1 ; # Function to return the count of required sub-strings def countSubStrings( str ): n = len ( str ) # Stores running count of 'x' starting from the end countX = [ 0 ] * n; count = 0 ; for i in range (n - 1 , - 1 , - 1 ): if ( str [i] = = 'x' ): count = count + 1 countX[i] = count # Next index of 'x' starting from index 0 nextIndexX = nextIndex( str , 0 , 'x' ) # Next index of 'y' starting from index 0 nextIndexY = nextIndex( str , 0 , 'y' ) # To store the count of required sub-strings count = 0 ; while (nextIndexX ! = - 1 and nextIndexY ! = - 1 ): # If 'y' appears before 'x' # it won't contribute to a valid sub-string if (nextIndexX > nextIndexY): # Find next occurrence of 'y' nextIndexY = nextIndex( str , nextIndexY + 1 , 'y' ) continue # If 'y' appears after 'x' # every sub-string ending at an 'x' appearing after this 'y' # and starting with the current 'x' is a valid sub-string else : count + = countX[nextIndexY] # Find next occurrence of 'x' nextIndexX = nextIndex( str , nextIndexX + 1 , 'x' ); # Return the count return count # Driver code s = "xyyxx" ; print (countSubStrings(s)); # This code is contributed by ihritik |
C#
// C# implementation of the approach using System; public class GFG { // Function that returns the index of next occurrence // of the character c in string str starting from index start static int nextIndex( string str, int start, char c) { // Starting from start for ( int i = start; i < str.Length; i++) { // If current character = c if (str[i] == c) return i; } // Not found return -1; } // Function to return the count of required sub-strings static int countSubStrings( string str) { int i, n = str.Length ; // Stores running count of 'x' starting from the end int []countX = new int [n]; int count = 0; for (i = n - 1; i >= 0; i--) { if (str[i] == 'x' ) count++; countX[i] = count; } // Next index of 'x' starting from index 0 int nextIndexX = nextIndex(str, 0, 'x' ); // Next index of 'y' starting from index 0 int nextIndexY = nextIndex(str, 0, 'y' ); // To store the count of required sub-strings count = 0; while (nextIndexX != -1 && nextIndexY != -1) { // If 'y' appears before 'x' // it won't contribute to a valid sub-string if (nextIndexX > nextIndexY) { // Find next occurrence of 'y' nextIndexY = nextIndex(str, nextIndexY + 1, 'y' ); continue ; } // If 'y' appears after 'x' // every sub-string ending at an 'x' appearing after this 'y' // and starting with the current 'x' is a valid sub-string else { count += countX[nextIndexY]; // Find next occurrence of 'x' nextIndexX = nextIndex(str, nextIndexX + 1, 'x' ); } } // Return the count return count; } // Driver code public static void Main() { string s = "xyyxx" ; Console.WriteLine(countSubStrings(s)); } // This code is contributed by Ryuga } |
PHP
<?php // PHP implementation of the approach // Function that returns the index of next occurrence // of the character c in string str starting from index start function nextIndex( $str , $start , $c ) { // Starting from start for ( $i = $start ; $i < strlen ( $str ); $i ++) { // If current character = c if ( $str [ $i ] == $c ) return $i ; } // Not found return -1; } // Function to return the count of required sub-strings function countSubStrings( $str ) { $n = strlen ( $str ); // Stores running count of 'x' starting from the end $countX = array (0, $n ,NULL); $count = 0; for ( $i = $n - 1; $i >= 0; $i --) { if ( $str [ $i ] == 'x' ) $count ++; $countX [ $i ] = $count ; } // Next index of 'x' starting from index 0 $nextIndexX = nextIndex( $str , 0, 'x' ); // Next index of 'y' starting from index 0 $nextIndexY = nextIndex( $str , 0, 'y' ); // To store the count of required sub-strings $count = 0; while ( $nextIndexX != -1 && $nextIndexY != -1) { // If 'y' appears before 'x' // it won't contribute to a valid sub-string if ( $nextIndexX > $nextIndexY ) { // Find next occurrence of 'y' $nextIndexY = nextIndex( $str , $nextIndexY + 1, 'y' ); continue ; } // If 'y' appears after 'x' // every sub-string ending at an 'x' appearing after this 'y' // and starting with the current 'x' is a valid sub-string else { $count += $countX [ $nextIndexY ]; // Find next occurrence of 'x' $nextIndexX = nextIndex( $str , $nextIndexX + 1, 'x' ); } } // Return the count return $count ; } // Driver code $s = "xyyxx" ; echo countSubStrings( $s ); ?> |
Javascript
<script> // Javascript implementation of the approach // Function that returns the index of next occurrence // of the character c in string str starting from index start function nextIndex(str,start,c) { // Starting from start for (let i = start; i < str.length; i++) { // If current character = c if (str[i] == c) return i; } // Not found return -1; } // Function to return the count of required sub-strings function countSubStrings(str) { let i, n = str.length; // Stores running count of 'x' starting from the end let countX = new Array(n); let count = 0; for (i = n - 1; i >= 0; i--) { if (str[i] == 'x' ) count++; countX[i] = count; } // Next index of 'x' starting from index 0 let nextIndexX = nextIndex(str, 0, 'x' ); // Next index of 'y' starting from index 0 let nextIndexY = nextIndex(str, 0, 'y' ); // To store the count of required sub-strings count = 0; while (nextIndexX != -1 && nextIndexY != -1) { // If 'y' appears before 'x' // it won't contribute to a valid sub-string if (nextIndexX > nextIndexY) { // Find next occurrence of 'y' nextIndexY = nextIndex(str, nextIndexY + 1, 'y '); continue; } // If ' y ' appears after ' x ' // every sub-string ending at an ' x ' appearing after this ' y ' // and starting with the current ' x ' is a valid sub-string else { count += countX[nextIndexY]; // Find next occurrence of ' x ' nextIndexX = nextIndex(str, nextIndexX + 1, ' x'); } } // Return the count return count; } // Driver code let s = "xyyxx" ; document.write(countSubStrings(s)); // This code is contributed by avanitrachhadiya2155 </script> |
Output
2
Complexity Analysis:
- Time Complexity: O(n2)
- Auxiliary Space: O(n), where n is the length of the string s.