2
\$\begingroup\$

Problem statement for finding given substring:

Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T.

Example:

S='adobecodebanc'
T='abc'
answer='banc'

How could I have improved the code from construction of code? Should I have created one more compare function? Did I use too many variables? Could I have optimized the code further and much more?

#include <iostream>
#include <stdio.h>

int min(int a, int b, int c);
int max(int a, int b, int c);

int main(void)
{
    char string1[] = "adobecodebanc";
    char *pstring = string1;
    int first_char = -1;
    int second_char = -1; 
    int third_char = -1;
    int final_distance = 1000;
    int final_min = 0;
    int final_max = 0;
    int counter = 0;

    /* iteratre over the string and compare each characeter*/
    while (*pstring != '\0')
    {
        /* if any character matches substring condition
           assign index value of the string to that variable  */
        if (*pstring == 'a' || *pstring == 'b' || *pstring == 'c')
        {
            if (*pstring == 'a')
            {
                first_char = counter;
            }
            else if (*pstring == 'b')
            {
                second_char = counter;
            }
            else
            {
                third_char = counter;
            }

            if (first_char != -1 && second_char != -1 && third_char != -1)
            {
                /* get the min and max index value difference*/
                int min_1 = min(first_char, second_char, third_char);
                int max_1 = max(first_char, second_char, third_char);
                int distance = max_1 - min_1;

                /*track the minimum substring so far*/
                if (distance < final_distance)
                {
                    final_distance = distance;
                    final_min = min_1;
                    final_max = max_1;
                }
            }
        }
        pstring++;
        counter++;
    }

    int temp = final_min;

    while (final_max >= temp)
    {
        std::cout << string1[temp];
        temp++;
    }
    std::cout << std::endl;
    return 0;
}

/* Find the min index value*/
int min(int first_char, int second_char, int third_char)
{
    if (first_char < second_char)
    {
        if (first_char < third_char)
        {
            return first_char;
        }
        else
        {
            return third_char;
        }
    }
    else
    {
        if (second_char < third_char)
        {
            return second_char;
        }
        else
        {
            return third_char;
        }
    }
}

/* Find the max index value*/
int max(int first_char, int second_char, int third_char)
{
    if (first_char > second_char)
    {
        if (first_char > third_char)
        {
            return first_char;
        }
        else
        {
            return third_char;
        }
    }
    else
    {
        if (second_char > third_char)
        {
            return second_char;
        }
        else
        {
            return third_char;
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$
  • There are already the functions std::min and std::max that you should use. It either takes 2 elements or an std::initializer_list, so you could use

    int min_1 = std::min({first_char, second_char, third_char});
    

    There is also std::minmax to get both the minimum and the maximum, possibly more efficiently than calling std::min and then std::max. Not that it matters for your application, but it is a good habit to get into.

    There is also std::none_of to check if none of first_char, second_char and third_char are -1, but the use is awkward because it needs a predicate.

  • Use range based for when possible. In this case you iterate over all the chars in the string, so it is easy:

    //while (*pstring != '\0')
    //for (const char c : string1)
    for (const char c : "adobecodebanc")
    
  • If you initialize first_char, second_char and third_char with std::numeric_limits<int>::min() you could leave out the check if all of them are not -1. You need to be careful for when printing though.

  • I assume this is supposed to be a general function for any string. If that string is "erf" the function prints "e". That doesn't seem right.

  • main(void) is considered bad style in C++. In C a function void f(); takes any number of arguments, so f(234, 2) compiles fine. To make that fail to compile you have to write void f(void). In C++ f(234, 2) doesn't compile and void f(void) is redundant, making you look like a C programmer trying out C++.

  • final_distance is initiated to "some big number". It makes sense to use std::numeric_limits<int>::max() instead of 1000.

  • Use const when it makes sense, for example for min_1, max_1 and distance.

  • Putting it all together it looks like this:

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    
    int main()
    {
        char string1[] = "adobecodebanc";
        int first_char = -1;
        int second_char = -1;
        int third_char = -1;
        int final_distance = std::numeric_limits<int>::max();
        int final_min = 0;
        int final_max = 0;
        int counter = -1;
    
        /* iteratre over the string and compare each characeter*/
        for (const char c : string1)
        {
            counter++;
            /* if any character matches substring condition
               assign index value of the string to that variable  */
            if (c == 'a')
            {
                first_char = counter;
            }
            else if (c == 'b')
            {
                second_char = counter;
            }
            else if (c == 'c')
            {
                third_char = counter;
            }
            else{
                continue;
            }
    
            if (first_char != -1 && second_char != -1 && third_char != -1)
            {
                /* get the min and max index value difference*/
                const auto minmax = std::minmax({first_char, second_char, third_char});
                const int distance = minmax.second - minmax.first;
    
                /*track the minimum substring so far*/
                if (distance < final_distance)
                {
                    final_distance = distance;
                    final_min = minmax.first;
                    final_max = minmax.second;
                }
            }
        }
    
        int temp = final_min;
    
        while (final_max >= temp)
        {
            std::cout << string1[temp];
            temp++;
        }
        std::cout << std::endl; //should not be needed since the program exits
        return 0; //gets implicitly added if you leave it out
    }
    

    I feel like I'm missing an obvious improvement, so I'll take a look again later.

\$\endgroup\$
  • \$\begingroup\$ Be aware that that for-range-loop also iterates over the terminator! \$\endgroup\$ – Deduplicator Nov 9 '15 at 1:56
  • \$\begingroup\$ Since you are using C++, please consider using std::string instead of char[]. \$\endgroup\$ – Juho Nov 9 '15 at 20:20
  • \$\begingroup\$ @mrm - thanks for reminder - hard to get over C habits :) \$\endgroup\$ – thedreamer Nov 9 '15 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.