Day 58 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/count-of-distinct-substrings/1

Count of distinct substrings

Difficulty: Medium Accuracy: 40.21%

Given a string s consisting of lowercase English characters, determine the total number of distinct non-empty substrings present in the string. A substring is defined as a contiguous block of characters within the string.
Two substrings are considered distinct if their contents differ, even if they originate from different positions in the string.
Note: The empty substring is not counted.
Examples :
Input: s = "ababa"
Output: 9
Explanation: All distinct substrings of "ababa" are: "a", "b", "ab", "ba", "aba", "bab", "abab", "baba", "ababa".
Input: s = "aaa"
Output: 3
Explanation: The distinct substrings of "aaa" are: "a", "aa", "aaa".
Constraints:
1 ≤ s.size() ≤ 3000

Solution:
class Solution:
def countSubs(self, s):
n = len(s)
suffixes = [(s[i:], i) for i in range(n)]
suffixes.sort()

    def lcp(a, b):
        c = 0
        while c < len(a) and c < len(b) and a[c] == b[c]:
            c += 1
        return c

    lcp_sum = 0
    for i in range(1, n):
        lcp_sum += lcp(suffixes[i][0], suffixes[i-1][0])

    total = n * (n + 1) // 2
    return total - lcp_sum