Shortest Subsequence

You are given a DNA sequence consisting of characters A, C, G, and T.

Your task is to find the shortest DNA sequence that is not a subsequence of the original sequence.

Example:

Input: s = "ACGTACGT"
Output: TTA

Approach

Java

public class ShortestSubsequence {
    public static void main(String[] args) {

        String s = "ACGTACGT";

        System.out.println(shortestSubsequence(s));

    }

    static String shortestSubsequence(String s) {
        int l = 0, r = 0;
        int a = 0, b = 0, c = 0, d = 0;
        int n = s.length();
        String res = "";
        while (l < n) {
            a = 0;
            b = 0;
            c = 0;
            d = 0;
            if (s.charAt(l) == 'A')
                a += 1;
            if (s.charAt(l) == 'C')
                b += 1;
            if (s.charAt(l) == 'G')
                c += 1;
            if (s.charAt(l) == 'T')
                d += 1;

            r = l + 1;
            while (r < n && a + b + c + d != 4) {
                if (s.charAt(l) == 'A')
                    a += 1;
                if (s.charAt(l) == 'C')
                    b += 1;
                if (s.charAt(l) == 'G')
                    c += 1;
                if (s.charAt(l) == 'T')
                    d += 1;
                r++;
            }
            if (a + b + c + d == 4)
                res += s.charAt(r - 1);
            l = r;
        }
        if (a + b + c + d == 4)
            res += 'A';
        else if (a == 0)
            res += 'A';
        else if (b == 0)
            res += 'C';
        else if (c == 0)
            res += 'G';
        else if (d == 0)
            res += 'T';
        return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

string shortestSubsequence(string s)
{
    int l = 0, r = 0;
    bool a = 0, b = 0, c = 0, d = 0;
    int n = s.size();
    string res = "";
    while (l < n)
    {
        a = 0, b = 0, c = 0, d = 0;
        a += (s[l] == 'A');
        b += (s[l] == 'C');
        c += (s[l] == 'G');
        d += (s[l] == 'T');
        r = l + 1;
        while (r < n && a + b + c + d != 4)
        {
            a += (s[r] == 'A');
            b += (s[r] == 'C');
            c += (s[r] == 'G');
            d += (s[r] == 'T');
            r++;
        }
        if (a + b + c + d == 4)
            res += s[r - 1];
        l = r;
    }
    if (a + b + c + d == 4)
        res += 'A';
    else if (!a)
        res += 'A';
    else if (!b)
        res += 'C';
    else if (!c)
        res += 'G';
    else if (!d)
        res += 'T';
    return res;
}
int main()
{

    string s = "ACGTACGT";

    cout << shortestSubsequence(s) << "\n";

    return 0;
}