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 startint 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-stringsint 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 codeint main(){ string s = "xyyxx"; cout << countSubStrings(s);}// This code is contributed by ihritik |
Java
// Java implementation of the approachpublic 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 startdef 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-stringsdef 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 codes = "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 startfunction 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-stringsfunction 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.
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!
