Number of occurence of two letters separted by a finit gap
I assume you are trying to find the number of pairs of a letter i and a letter j (i and j are arbitrary letters) that are at most L indices away from each other.

Use a sliding window algorithm. The sliding window will contain all indexes of an element i that are within the range of a certain index with the letter j.

Step 1. Store all indexes of the letter i in a sorted fashion (scan the input in order) O(N) 

Step 2. Store all indexes of the letter j in a sorted fashion (similar to Step 1) O(N)

Example:

string s;  &lt;- Assume input is already in this string
vector&lt;int&gt; letter1, letter2; &lt;- Store indices
for (int i = 0; i &lt; N; i++){
    if (s[i] == 'a'){         &lt;- Our letter 'i'
        letter1.push_back(i);
    }
    if (s[i] == 'c'){         &lt;- Our letter 'j'
        letter2.push_back(i);
    }
}


Step 3 (more complicated):

int track = 0, sum = 0;    &lt;- Track the front-most index and the running sum of pairs
queue&lt;int&gt; window;  &lt;- Our sliding window
for (int i = 0; i &lt; letter2.size(); i++){   &lt;- For every letter 'j'
    while (!window.empty() &amp;&amp; window.front() &lt; (letter2[i] - L)){
        window.pop_front();
    }
    while (letter1[track] &lt;= (letter2[i] + L) &amp;&amp; (letter1[track] &gt;= (letter2[i] - L)){
        window.push(letter1[track]);
        track++;
    }
    sum = sum + window.size();
}


Let me explain some of the lines.

while (!window.empty() &amp;&amp; window.front() &lt; (letter2[i] - L)){
    window.pop_front();
}


The condition !window.empty() is to prevent a run-time error when calling window.front() later on. window.front() &lt; (letter2[i] - L) implies that the smallest index in the queue is less than the minimum allowed value in the range, thus we should exclude it. We do not have to consider it ever again as the smallest possible value in the allowed range only increases as we iterate over letter2. We continue removing the elements till all of the elements are within the range or there are no elements left.

while (track &lt; letter1.size() &amp;&amp; letter1[track] &lt;= (letter2[i] + L)  ){
    if ((letter1[track] &gt;= (letter2[i] - L)) window.push(letter1[track]);
    track++;
}


The first condition track &lt; letter1.size() is also to prevent a run-time error. The next condition is to check if the element is less than or equal the maximum allowed value in the range. If the element is also more than or equal to the smallest allowed value in the range, then we add it to the queue. We still increment track even if no value is pushed into the queue as at the end of each iteration of the loop, letter1[track] is always the smallest element larger than the allowed range during that iteration or is out of bounds.

All you have to do after this to output sum.

Although there are 2 nested loops, this algorithm runs in O(N) where N is the number of letters. Why? Because each index of the letter i is pushed and popped from the queue at most once each throughout the entire loop. This is at most 2*N operations, which is linear time.

All of the code is in C++ as that is my main language, though the concept can be applied to any language. You might want to look up other examples of the sliding window algorithm like this question from the Australian Informatics Olympiad.