Problem Statement:
There is a String s which has a few (maybe none) '1's in it. Get all triplets of such '1's which are equidistant to each other. Output the triplet with the maximum distance 'k' between them.
Solution:
We first need to find the maximum value of distance 'k' between triplets of '1's present in the String. Obviously, the maximum possible value of k will be half the string length. So we will iterate over the value of k from s.length()/2 down to 1. We then iterate over the string to check for '1's and checking whether the characters at distances of k and 2k are also '1's.
Clearly, there are 2 variables whose iterations will determine the time complexity of the problem viz. 'k' and the string itself which needs to be traversed. Thus, one solution could be to decide on a value of 'k' in the outer loop and then traverse the string to see if this 'k' contains triplets of one.
Algorithm1{
for k = string.length/2 down to 1 :
for i = 0 up to string.length-2k :
if string[i]=string[i+k]=string[i+2k]=1 :
output k;
}
Another solution could be to decide on an index in the string and then traverse over the string using different values of 'k'.
Algorithm2{
for i = 0 upto string.length-2 :
for k = string.length/2 down to 1 :
if i+2k < string.length AND string[i]=string[i+k]=string[i+2k]=1 :
maxK = k; break;
output maxK;
}
Both the solutions are asymptotically equally fast and have a time complexity of O(n2) in the average case.
However, if one observes carefully, the former method might yield faster results in cases where the answer is closer to the length of the string. This is because 'k' is decremented steadily in the former algorithm and is oputputted as soon as the condition is satisfied. This results in lesser conditional checks and in turn lesser array elements accesses leading to lesser running time.This fact, however, will not be reflected in the asymptotic performance of the algorithm, since asymptotically, it will remain O(n2) owing to the nested for loops.
Below is the Java code for the former algorithm:
There is a String s which has a few (maybe none) '1's in it. Get all triplets of such '1's which are equidistant to each other. Output the triplet with the maximum distance 'k' between them.
Solution:
We first need to find the maximum value of distance 'k' between triplets of '1's present in the String. Obviously, the maximum possible value of k will be half the string length. So we will iterate over the value of k from s.length()/2 down to 1. We then iterate over the string to check for '1's and checking whether the characters at distances of k and 2k are also '1's.
Clearly, there are 2 variables whose iterations will determine the time complexity of the problem viz. 'k' and the string itself which needs to be traversed. Thus, one solution could be to decide on a value of 'k' in the outer loop and then traverse the string to see if this 'k' contains triplets of one.
Algorithm1{
for k = string.length/2 down to 1 :
for i = 0 up to string.length-2k :
if string[i]=string[i+k]=string[i+2k]=1 :
output k;
}
Another solution could be to decide on an index in the string and then traverse over the string using different values of 'k'.
Algorithm2{
for i = 0 upto string.length-2 :
for k = string.length/2 down to 1 :
if i+2k < string.length AND string[i]=string[i+k]=string[i+2k]=1 :
maxK = k; break;
output maxK;
}
Both the solutions are asymptotically equally fast and have a time complexity of O(n2) in the average case.
However, if one observes carefully, the former method might yield faster results in cases where the answer is closer to the length of the string. This is because 'k' is decremented steadily in the former algorithm and is oputputted as soon as the condition is satisfied. This results in lesser conditional checks and in turn lesser array elements accesses leading to lesser running time.This fact, however, will not be reflected in the asymptotic performance of the algorithm, since asymptotically, it will remain O(n2) owing to the nested for loops.
Below is the Java code for the former algorithm:
