# Find a substring with minimum distance

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'


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 *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
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;
}
}
}


• 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()
{
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
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.

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