Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Approach
3.1.
Input
3.2.
Output
3.3.
Time Complexity
3.4.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

Queuing Problem

Author Saksham Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

If you like sports, then the best mental sport out there is competitive programming. Here complex algorithms are used to solve complex problems, but it's equally fun as well. Most of the students fear competitive coding, but you don’t have to worry as your Ninja friend is here. Thus to sharpen your concepts, today, we will discuss one such problem, i.e., Queueing Problem, where your concepts related to programming and maths would be judged. Let’s first understand the problem better.

Understanding the Problem

We have been given a string ‘S’, which is initially empty, and we have been given ‘N’ number of operations to perform on the string. In each operation (depending upon the input)

  • We can either add a character to the end of the string S. Input will be given using a ‘+’ character followed by the character need to be added.
  • We can either delete the first character of S. Input will be given using a ‘-’ character.

Our task is to print the sum of the number of distinct substrings of string ‘S’ after each operation.

Let’s understand this better by the following example.

Input

4
+ a
+ b
-
+ a

Output

8

Explanation

After the first operation
S = a
Number of substrings = 1 (a)

After the second operation
S  = ab
Number of substrings = 3 (a, b, ab)

After the third operation 
S = b
Number of substrings = 1 (b)

After the fourth operation
S = ab
Number of substrings = 3 (a, b, ab)

Thus total sum is 1 + 3 + 1 + 3 = 8.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The idea is to use the Suffix Tree, which is quite obvious as we have to deal with multiple queries.

But how?

First, we have to build the suffix array.

  • We will read all the queries and ignore the ‘-’ to get the complete string first, and then we can reverse it to form our Suffix Array. So now,
    • Query ‘+’ will stand to add a Suffix longer than all the existing ones while query ‘-’ will stand for delete the last char in all the suffix that is present.

Then we will proceed on building the segment tree with the following rules:

  • The order of suffixes will be the same as they have in the suffix array.
  • No suffix will be a prefix of other suffixes.
  • Now let’s say we have any suffix, say ‘CUR’, and its previous suffix ‘PRE’, we will maintain and store Len(CUR) - LCP(CUR, PRE) for CUR(Let’s say this is ‘RL’). The same will be done for its next prefix. I.e., Len(CUR) - LCP(CUR,NEXT).(Let’s say this is ‘RR’) Here, LCP stands for the longest common prefix where whereas Len stands for the length of the string.

Now let’s talk about the remaining operations.

  • When we add a new suffix, say ‘CUR’, we will check its previous suffix and the next suffix if either of them is the prefix of CUR. We will delete it.
  • Now, whenever we have to delete a char from the suffix, we will see that all the RR and RL are reduced by 1. If any of them becomes 0, then we will delete it. 
  • Also answer at any instant is the sum of (Len(CUR) - LCP(CUR, PRE)) and ( Len(CUR) - LCP(CUR,NEXT)).i.e., ‘RL’ - ‘RR’ .This will be maintained in segment tree.

This might be a little overwhelming, but code will surely help you to grasp everything. Let us see the code.

Code

#include <cstdio>
#include <queue>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
using int64 = long long;

const int mod = 1e9 + 7;
const int N = 1e6 + 10,
    inf = 1e9;

struct SuffixTree
{
    struct node
    {
        // Following suffix link will lead to the vertex corresponding to the same substring, but without the first character.
        node *go[26], *link, *fa;
        int cnt, st, len;
        node() {}
        void clr()
        {
            st = cnt = 0;
            len = inf;
            link = fa = NULL;
            memset(go, 0, sizeof(go));
        }
    }
    pool[N *2], *rt, *ptr;
    int s[N], n;
    int64 dsc;
    std::queue<node*> leaf;

    struct position
    {
        node * u;
        int cur;
        int pos;
        int rem;
        position() {}
        void go(int o)
        {
            u = u->go[o];
            pos -= u->len;
            cur += u->len;
        }
        bool can(int o)
        {
            return u->go[o] && pos >= u->go[o]->len;
        }
    }
    last;

    // For new node.
    node* new_node(node *fa, int st, int len)
    {
        ptr->clr();
        ptr->fa = fa;
        ptr->st = st;
        ptr->len = len;
        if (fa) fa->cnt++;
        return ptr++;
    }

    // Initializing.
    void init()
    {
        n = 0, ptr = pool;
        last.u = rt = new_node(NULL, 0, inf);
        last.cur = last.pos = last.rem = 0;
        dsc = 0;
    }

    void walk()
    {
        while (last.can(s[last.cur]))
        {
            last.go(s[last.cur]);
        }
    }
    void follow_link()
    {
        if (last.u == rt)
        {
            if (last.pos) --last.pos, ++last.cur;
        }
        else last.u = last.u->link ? last.u->link : rt;
        --last.rem;
    }
    void add(int c)
    {
        s[n++] = c;
        ++last.rem;
        assert(last.pos >= 0);
        for (node *p = rt; last.rem;)
        {
            if (!last.pos) last.cur = n - 1;
            walk();
            int o = s[last.cur];
            node* &v = last.u->go[o];
            int t = s[v == NULL ? 0 : v->st + last.pos];
            if (v == NULL)
            {
                assert(last.pos == 0);
                v = new_node(last.u, n - 1, inf);
                leaf.push(v);
                p->link = last.u;
                p = rt;
            }
            else if (t == c)
            {
                p->link = last.u;
                ++last.pos;
                return;
            }
            else
            {
                // split edge
                node *u = new_node(last.u, v->st, last.pos);
                last.u->cnt--;
                u->go[c] = new_node(u, n - 1, inf);
                leaf.push(u->go[c]);
                u->go[t] = v;
                ++u->cnt;
                v->fa = u;
                v->st += last.pos;
                v->len -= last.pos;
                p->link = v = u;
                p = u;
            }
            follow_link();
        }
    }
    void del()
    {
        if (last.pos) walk();
        auto x = leaf.front();
        leaf.pop();
        for (; x != last.u && !x->cnt; x = x->fa)
        {
            dsc -= std::min(n - x->st, x->len);
            auto p = x->fa;
            p->go[s[x->st]] = NULL;
            p->cnt -= 1;
        }
        if (last.rem && x == last.u)
        {
            if (!last.pos && !x->cnt)
            {
                dsc -= std::min(n - x->st, x->len);
                if (x->len != inf)
                {
                    x->st = n - x->len;
                    x->len = inf;
                }
                dsc += std::min(n - x->st, x->len);
                leaf.push(x);
            }
            else if (last.cur < n && !x->go[s[last.cur]])
            {
                auto u = new_node(x, n - last.pos, inf);
                x->go[s[last.cur]] = u;
                dsc += std::min(n - u->st, u->len);
                leaf.push(u);
            }
            else
            {
                return;
            }
            follow_link();
        }
    }
    void print(node *o)
    {
        printf("idx=%ld st=%d len=%d suf=%ld\n", o - pool, o->st, o->len, o->link ? o->link - pool : -1);
        for (int i = 0; i < 26; ++i)
            if (o->go[i])
            {
                assert(o->go[i]->fa == o);
                printf("%ld -> %ld\n", o - pool, o->go[i] - pool);
                print(o->go[i]);
            }
    }
    void solve()
    {
        init();
        int q;
        scanf("%d", &q);
        int64 ret = 0;
        for (int i = 0; i < q; ++i)
        {
            char op;
            scanf(" %c", &op);
            if (op == '+')
            {
                char c;
                scanf(" %c", &c);
                add(c - 'a');
                dsc += leaf.size();
            }
            else
            {
                del();
            }
            ret += dsc % mod;
        }
        printf("%lld\n", ret % mod);
    }
}
suffix_tree;

int main()
{
    suffix_tree.solve();
    return 0;
}

Input

4
+ a
+ b
-
+ a

Output

8

Time Complexity

O(Q * log (Q)), where ‘Q’ is the number of queries.
This is because we are using a segment tree, and we will make a total of Q queries, and for each query, it will cost us log (Q) time, which is the usual time taken by inserting and deleting of segment tree. Thus, the overall time complexity is O(Q * log(Q)).

Space Complexity

O((2 * Q) - 1)where ‘Q’ is the number of queries.
As we are using a suffix array, there will be a total of Q nodes.

Check out this problem - Longest Common Prefix

Key Takeaways

We saw how we solved the ‘Queuing problem’ using suffix trees in a very reduced time. It was hard to grasp, but we are proud that our ninja helped you in understanding it. Now, You must be thrilled about learning a new concept, but the road to become a competitive coder is still very long. So head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. You can also consider our competitive programming course to give your career an edge over others. Till then, Happy Coding!

Previous article
Length of Longest Substring Occurring in a Given Substring at Least ‘K’ Times
Next article
Find the Median of BST in O(N) Time and O(1) Space
Live masterclass