Given a string str of N characters, the task is to calculate the count of valid unordered pairs of (i, j) such that the string after deleting ith character is equal to the string after deleting the jth character.
Examples:
Input: str = “aabb”
Output: 2
Explanation: The string after deletion of 1st element is “abb” and the string after deletion of 2nd element is “abb”. Similarly, the string after deletion of 3rd element is “aab” and the string after deletion of 4th element is “aab”. Hence, the number of valid pairs of (i, j) are 2, i.e, (1, 2) and (3, 4).Input: str = “aaaaaa”
Output: 15
Approach: The given problem can be solved using the following observations:
- If Si = Sj, then Si = Si+1 = Si+2 … = Sj must hold true.
- Also if Si = Sj, then str[i] = str[i+1] = str[i+2] … = str[j] must hold true as well.
Therefore, using the above observations, the two-pointer technique can be used to calculate the intervals (l, r) in the string str such that str[l] = str[l+1] … = str[r], and for each valid (l, r), the count of valid pairs will be r – lC2.
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 count of valid// pairs (i, j) such that string after// deleting ith character is equal to// string after deleting jth characterint countValidPairs(string str, int N){ // Stores the required count int ans = 0; // Loop to iterate the given array for (int l = 0, r; l < N; l = r) { // initial end point r = l; // Loop to calculate the range // [l, r] such that all characters // from l to r are equal while (r < N && str[l] == str[r]) { r++; } // Update the answer ans += ((r - l) * (r - l - 1)) / 2; } // Return Answer return ans;}// Driver Codeint main(){ string str = "aaaaaa"; cout << countValidPairs(str, str.length()); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Function to find the count of valid// pairs (i, j) such that string after// deleting ith character is equal to// string after deleting jth characterstatic int countValidPairs(String str, int N){ // Stores the required count int ans = 0; // Loop to iterate the given array for (int l = 0, r; l < N; l = r) { // initial end point r = l; // Loop to calculate the range // [l, r] such that all characters // from l to r are equal Character c1 = str.charAt(l); Character c2 = str.charAt(r); while (r < N && c1.equals(c2)) { r++; } // Update the answer ans += ((r - l) * (r - l - 1)) / 2; } // Return Answer return ans;}// Driver Codepublic static void main(String args[]){ String str = "aaaaaa"; System.out.print(countValidPairs(str, str.length()));}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach# Function to find the count of valid# pairs (i, j) such that string after# deleting ith character is equal to# string after deleting jth characterdef countValidPairs(str, N): # Stores the required count ans = 0; # Loop to iterate the given array l = 0; r = None; while(l < N): # initial end point r = l; # Loop to calculate the range # [l, r] such that all characters # from l to r are equal while (r < N and str[l] == str[r]): r += 1 # Update the answer ans += ((r - l) * (r - l - 1)) // 2; l = r; # Return Answer return ans;# Driver Codestr = "aaaaaa";print(countValidPairs(str, len(str)));# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the count of valid// pairs (i, j) such that string after// deleting ith character is equal to// string after deleting jth characterstatic int countValidPairs(string str, int N){ // Stores the required count int ans = 0; // Loop to iterate the given array for (int l = 0, r; l < N; l = r) { // initial end point r = l; // Loop to calculate the range // [l, r] such that all characters // from l to r are equal char c1 = str[l]; char c2 = str[r]; while (r < N && c1.Equals(c2)) { r++; } // Update the answer ans += ((r - l) * (r - l - 1)) / 2; } // Return Answer return ans;}// Driver Codepublic static void Main(){ string str = "aaaaaa"; Console.Write(countValidPairs(str, str.Length));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to find the count of valid// pairs (i, j) such that string after// deleting ith character is equal to// string after deleting jth characterfunction countValidPairs(str, N){ // Stores the required count let ans = 0; // Loop to iterate the given array for (let l = 0, r; l < N; l = r) { // initial end point r = l; // Loop to calculate the range // [l, r] such that all characters // from l to r are equal while (r < N && str[l] == str[r]) { r++; } // Update the answer ans += ((r - l) * (r - l - 1)) / 2; } // Return Answer return ans;}// Driver Codelet str = "aaaaaa";document.write(countValidPairs(str, str.length));// This code is contributed by Samim Hossain Mondal.</script> |
Output
15
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
