Count of strings that do not contain Arc intersection

Yukti Kumari
Last Updated: May 13, 2022

Introduction

In this article, we will see a very interesting question based on binary strings. We will solve it very intuitively and start with a brute force approach. Next, we will optimize the solution to reach a better time complexity.
 

Let’s get started with the problem statement.

Problem Statement

You are given an array arr[] consisting of binary strings; the task is to count the number of strings that do not contain any Arc Intersection.

First, let’s understand the problem statement. 

 

What is a binary string?

The string, which consists of at most two unique characters, is called a binary string.

E.g., S=”110011” - It has only 0 and 1 as unique characters.

       S=”ABBAAB” - Consists of two characters A and B.

While the string S=”ABCAABB” is not a binary string because it has 3 unique characters. 

 

Now, the next term present in the problem statement is Arc Intersection. 

 

What do we mean by arc intersection in a binary string?

In a binary string, if every two consecutive same characters are connected by an arc, then if any two arcs intersect then it implies that there is an arc intersection.

Consider the string S = “110011”.

The first 1 is connected to the second 1 by an arc. Then third 0 is joined by an arc with 4th 0. We see that the three arcs do not intersect. So, the given string does not contain arc intersection.

 

Next, consider another string S=”ABBABAB”.

 

 

Please try to solve this problem on your own before moving on to further discussion here

 

We will use a stack to check if there is an arc intersection present in a binary string.

 

Let’s see the flow of the algorithm - 

  1. Define a variable count to store the number of desired strings and initialize it with 0.
     
  2. Define a stack which we will use to store the characters of the binary string.
     
  3. Now, iterate through the array of strings and pick a binary string one by one.
     
  4. For a binary string iterate through its characters.
     
  5. Check if the stack is empty. If so, push the current character to the stack. Or If the stack is not empty and the stack top matches with the current character then pop the stack top. Observe that by doing this we get rid of the arc formed by the two characters.  In the case when the stack top does not match with the current character, push the current character to the stack.
     
  6. Repeat step 5 for all the characters of the string.
     
  7. In the end, check if the stack is empty or not. If it is empty, then the string does not contain arc intersection and increment the count by 1. Else, it has an arc intersection.

 

Let’s see the code implementation along with the analysis of time and space complexity in the next section.

C++ Implementation

/*C++ code to find the count of strings which does not contain an arc intersection*/
#include <bits/stdc++.h>
using namespace std;


int checkArcIntersection(string S)
{
    int len = S.length();
    stack<char> stk;
    for (int i = 0; i < len; i++)
    {
        if (stk.empty() || stk.top() != S[i])
        {
            stk.push(S[i]);
        }
        else if (!stk.empty() && stk.top() == S[i])
        {
            stk.pop();
        }
    }


    if (stk.empty())
        return 1;
    return 0;
}


void cntBinaryStrings(string binaryStrings[], int n)
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        count += checkArcIntersection(
            binaryStrings[i]);
    }
    cout << "The count of strings which does not contain an arc intersection is: " << count << endl;
}


int main()
{
    int n = 4;
    string binaryStrings[n] = {"ABBAABAB", "110011", "0101", "AABB"};
    cntBinaryStrings(binaryStrings, n);
}

 

Output

The count of strings which does not contain an arc intersection is: 2

Time Complexity

O(n*m), where n is the number of binary strings in the given array and m is the length of the longest string. We have one loop of length n to iterate over all the strings and within that, we call the function checkArcIntersection which iterates over all the characters of the string using a loop of length m. So, this results in two nested loops hence the time complexity is O(n.m).

Space Complexity 

In the function checkArcIntersection , we use a stack of length equal to the length of the string. So, if the maximum length of a string is M, then the space complexity will be O(M).
 

Frequently Asked Questions

  1. What is a stack?
    stack is an abstract data type that serves as a collection of elements and has two primary operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that has not yet been removed.
     
  2. What is stack pop ()?
    Stack pop() removes the most recently added element that has not yet been removed.
     
  3. Where can I practice more stack problems?
    You can use CodeStudio to practise a wide range of DSA questions typically asked in interviews at big MNCs.

 

Key Takeaways

In this article, we solved a quite interesting problem to count the strings having no arc intersection. We used stacks to solve this problem efficiently. 

Observe that this problem was quite similar to the problem of checking balanced parenthesis. 

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think