LeetCode 2083: Substrings That Begin and End With the Same Letter Solution

Master LeetCode problem 2083 (Substrings That Begin and End With the Same Letter), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2083. Substrings That Begin and End With the Same Letter

Medium

Hash Table Math String Counting Prefix Sum

Problem Explanation

Explanation:

Given a string, we need to find the number of substrings that begin and end with the same letter. We can achieve this by iterating through the string and counting the occurrences of each character. For each character, we can determine the number of substrings that begin and end with that character by multiplying the count of occurrences of that character by one less than that count and then dividing by 2. This is because for each character, we can form substrings by selecting the starting and ending positions in different ways.

Algorithm:

Initialize a count variable to store the total count of substrings that begin and end with the same letter.
Iterate through the string and count the occurrences of each character.
For each character, add the count of occurrences multiplied by one less than that count, and then divide by 2 to get the total number of substrings that begin and end with that character.
Return the total count of substrings.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input string.

Space Complexity:

The space complexity of this algorithm is O(1), as we are using a constant amount of extra space.

Solution Code

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        
        for (char c = 'a'; c <= 'z'; c++) {
            int charCount = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == c) {
                    charCount++;
                }
            }
            
            count += (charCount * (charCount - 1)) / 2;
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2083 (Substrings That Begin and End With the Same Letter)?

This page provides optimized solutions for LeetCode problem 2083 (Substrings That Begin and End With the Same Letter) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2083 (Substrings That Begin and End With the Same Letter)?

The time complexity for LeetCode 2083 (Substrings That Begin and End With the Same Letter) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2083 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2083 in Java, C++, or Python.

Back to LeetCode Solutions