Counting binary substrings The exercise i am working on requires me to read a binary sequence stored in a text file. The objective is to find the occurrences of all subsequences of length between a and b (their values are given in the function parameters) and put them in a list of tuples.
For example: If the following binary sequence is given as input and the length of each subsequence should be between 2 and 4:
a = 2 
b = 4 

01010010010001000111101100001010011001111000010010011110010000000

I should write a program to generate the following output:
[(1, [&quot;1011&quot;, &quot;1101&quot;]), 
 (2, [&quot;0101&quot;, &quot;0110&quot;, &quot;1010&quot;]), 
 (3, [&quot;0111&quot;, &quot;101&quot;, &quot;1110&quot;, &quot;1111&quot;]), 
 (4, [&quot;0001&quot;, &quot;0011&quot;, &quot;1100&quot;]), 
 (5, [&quot;011&quot;, &quot;1000&quot;, &quot;110&quot;]), 
 (6, [&quot;0000&quot;, &quot;111&quot;]), 
 (7, [&quot;0010&quot;, &quot;1001&quot;]), 
 (8, [&quot;0100&quot;]), 
 (10, [&quot;010&quot;]), 
 (11, [&quot;000&quot;, &quot;001&quot;, &quot;11&quot;]), 
 (12, [&quot;100&quot;]),            
 (15, [&quot;01&quot;, &quot;10&quot;]), 
 (23, [&quot;00&quot;] )]

You will notice that each tuple in the list has two elements. The first element is the number of times a subsequence appears in the given sequence whilst the second element is the list containing the corresponding subsequences.
E.g. the first tuple indicates that the subsequences &quot;1011&quot; and &quot;1101&quot; appear only once in the given sequence.
The solution i have written does solve the problem (it passes all correctness tests), but it is slow and doesn't pass the performance tests (it only passes 5 out of 22 tests) in which the maximum timeout is set to 1 second. How could i make this solution faster?
I am not allowed to import any external libraries.
def ex1(ftesto,a,b,n):
    with open(ftesto,encoding='utf8') as f: 
        S = f.read().replace('\n','')
    N = len(S)
    D = {} 
    subsequences = {} 
    for i in range(N+1):
        for j in range(i+1,N+1): 
            if a &lt;= len(S[i:j]) &lt;= b: 
                if S[i:j] not in D:
                    D[S[i:j]] = 1   
                else:
                    D[S[i:j]] += 1                     
    for k,v in D.items(): 
        subsequences.setdefault(v,[]).append(k)
    result = sorted([(k,sorted(v)) for k,v in subsequences.items()])   
    return result[:n] 

if __name__ == '__main__':
    
   ftesto = 'ft1.txt'
   a = 2
   b = 4
   n = 20

The amount of elements in the list must be equal or less than &quot;n&quot;. That explains why i am using the slicing at the end of the function.
PEP 8
You are violating several Style Guide for Python Code rules:

commas should be followed by a space,
variables should be snake_case,
always surround binary operators with one space

Never called
ex1() is never called by your mainline.
Declare variables closer to where they are used
subsequences is declared 7 lines earlier than it needs to be.
Separate I/O from processing
ex1() cannot be called with test data, unless that test data is in a file.  Use two functions.  One that solves the problem with an in-memory string, and a second that reads the string from a file for processing.
Avoid dict.setdefault(...)
subsequences.setdefault(v, []).append(k) will create a new list ([]) every time it is executed.  Many times this default will never be used, and must be garbage collected.  This is just wasting time.
Instead, use collections.defaultdict.  Note that collections is not an external library; it is internal, built into Python.
Counter
Similarly, use collections.Counter for counting objects.  Again, built into Python; not an external library.
Reworked Code

from collections import Counter, defaultdict

def binary_sequence_counts(sequence, shortest, longest, limit):
    n = len(sequence)

    sequence_counter = Counter()
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            if shortest &lt;= len(sequence[i:j]) &lt;= longest:
                sequence_counter[sequence[i:j]] += 1

    subsequences = defaultdict(list)
    for subsequence, count in sequence_counter.items():
        subsequences[count].append(subsequence)

    result = sorted((count, sorted(subseqs)) for count, subseqs in subsequences.items())
    return result[:limit]

def ex1(ftesto, a, b, n):
    with open(ftesto, encoding='utf8') as f:
        sequence = f.read().replace('\n', '')

    return binary_sequence_counts(sequence, a, b, n)

def testcase():
    seq = &quot;01010010010001000111101100001010011001111000010010011110010000000&quot;
    result = binary_sequence_counts(seq, 2, 4, 20)
    # print result, or
    # check if result is correct


The above code is way more readable than the original.
Efficiency
This code is just plain awful:
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            if shortest &lt;= len(sequence[i:j]) &lt;= longest:
                ...

If your sequence is 100,000 digits long, the inner loop will execute about 5,000,000,000 times!  That's a lot!  Especially if you're only concerned with subsequences between 2 and 4 digits long, in which case you only need about 300,000 iterations.
A simple modification of the range(...) limits would dramatically improve your speed.  If you do it correctly, you can even get rid of the a &lt;= len(...) &lt;= b test, because with the correct ranges you will not be able to generate sequences that are the incorrect length.
In fact, with the correct limits, you could even use the counter to do the counting entirely for you:
sequence_counts = Counter(sequence[i:j]
                          for i in range(...)
                          for j in range(...))

Proper range limits left as exercise to student.
min heap
You are sorting a potentially huge list of values, and then returning only the n-smallest results.  sorted(iterable)[:n]  This can be a potentially huge waste of time!
Using the heapq.nsmallest(n, iterable) (again, built-in, not an external library), you can reduce the amount of space used, and possibly the amount of time.  Note that this is faster only for smaller values of n.  If n is big, it can be faster to use sorted(iterable)[:n].  Always profile!
Roll Your Own
The question has been updated to disallow any imports.  No problem.  We'll just have to implement our own defaultdict and Counter.
Assuming your are allowed to create your own class ...
object.__missing__
When a dict.__getitem__ is called, but the dictionary does not contain that key, object.__missing__(self, key) is called.  We can use this method to change the behaviour.
Counter
To implement a simple &quot;counter&quot; dictionary, we just need 0 to be returned for any missing key.
class Counter(dict):
    def __missing__(self, key):
        return 0

If the key is missing, 0 is returned.  If you &quot;add 1&quot; to a missing key, 0 is returned, 1 is added to the returned value, and the resulting 1 is stored back under that key:
&gt;&gt;&gt; c = Counter()
&gt;&gt;&gt; c['foo']
0
&gt;&gt;&gt; c['bar'] += 1
&gt;&gt;&gt; c['bar'] += 1
&gt;&gt;&gt; c
{'bar': 2}

Notice that the 'foo' key still does not exist; only the 'bar' key exists because values were actually written to it.
defaultdict
You don't actually need a full defaultdict here.  You just need a dictionary which returns an empty list when an unknown key is retrieved.  Unlike the Counter class above, we need to remember the list that was returned for the key, because we'll be appending items to the list, which (unlike the += operator) won't write the result back into the dictionary.
class DictOfLists(dict):
    def __missing__(self, key):
        self[key] = []
        return self[key]

Unlike the Counter, referencing an unknown key will create the key in the dictionary, filling it with an empty list:
&gt;&gt;&gt; dol = DictOfLists()
&gt;&gt;&gt; dol['foo']
[]
&gt;&gt;&gt; dol['bar'].append(&quot;baz&quot;)
&gt;&gt;&gt; dol
{'foo': [], 'bar': ['baz']}
&gt;&gt;&gt; 

The actual defaultdict allows you to specify a factory function in the constructor, to create values for the missing keys.  That isn't too much more complicated.  Feel free to research this.