Substrings with same first and last characters

JavaView on GFG

Time: O(n)

Space: O(26)

Intuition

Count substrings where first and last character are equal. Frequency of each character.

Algorithm

1For each character c with frequency f: contributes f*(f+1)/2 substrings (choose 2 positions + all single-char substrings).

Common Pitfalls

•Count frequency of each character. Single character counts as valid (same first and last). Formula: f*(f+1)/2.

Substrings with same first and last characters.java

Java

// Approach: Count frequency of each character. For each char with count c, it contributes c*(c+1)/2 substrings.
// Time: O(n) Space: O(26)
import java.util.*;

class Solution {
    public int countSubstring(String s) {
        int n = s.length();
        int count = 0;
        HashMap<Character, Integer> ans = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            ans.put(ch, ans.getOrDefault(ch, 0) + 1);
            count += ans.get(ch);
        }
        return count;
    }
}

Was this solution helpful?