Substrings with same first and last characters

JavaView on GFG

Time: O(n)

Space: O(26)

Problem Overview

Count substrings where first and last character are equal.

See our study guide for structured GFG and LeetCode practice.

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?