Count Substrings Starting and Ending with Given Character

• Initialize a counter variable count to 0.
• Use a nested loop structure. The outer loop with index i iterates from 0 to n-1 (where n is the string length) to select a starting character.
• The inner loop with index j iterates from i to n-1 to select an ending character.
• Inside the loops, check if s.charAt(i) is equal to the target character c AND s.charAt(j) is also equal to c.
• If both conditions are true, it means we have found a valid substring. Increment the count.
• After both loops have finished, return the total count.

The algorithm uses two nested loops to define the start and end points of every substring. The outer loop, with index i, iterates from the beginning to the end of the string, marking the potential start of a substring. The inner loop, with index j, iterates from i to the end of the string, marking the potential end of a substring. A substring is valid if the characters at both the start index i and the end index j are equal to the target character c. We maintain a counter that is incremented for every such valid pair of indices (i, j).

1class Solution {2    public long countSubstrings(String s, char c) {3        long count = 0;4        int n = s.length();5        for (int i = 0; i < n; i++) {6            for (int j = i; j < n; j++) {7                if (s.charAt(i) == c && s.charAt(j) == c) {8                    count++;9                }10            }11        }12        return count;13    }14}

• Initialize a counter k to 0. It's important to use a 64-bit integer type (like long in Java) for this counter to avoid potential overflow.
• Iterate through the input string s just once, from the first character to the last.
• In each iteration, check if the current character is equal to the target character c.
• If it is, increment the counter k.
• After the loop finishes, k will hold the total number of occurrences of c in the string.
• The total number of valid substrings is the sum of integers from 1 to k. This can be calculated directly using the formula for the sum of an arithmetic series: (k * (k + 1)) / 2.
• Return this calculated value.

The core idea is that any substring starting and ending with c is uniquely defined by the indices of its starting and ending c. Let's say the character c appears k times in the string. The first occurrence of c can form a valid substring with itself and the k-1 other occurrences of c that appear after it, resulting in k substrings. The second occurrence of c can form a valid substring with itself and the k-2 occurrences after it, giving k-1 substrings. This pattern continues until the last occurrence of c, which can only form a substring with itself (1 substring). The total count is the sum k + (k-1) + ... + 1. This is the sum of the first k positive integers, which has a well-known formula: k * (k + 1) / 2. The algorithm is thus to first count occurrences of c and then apply this formula. Note that the result can be large, so a 64-bit integer type (long) should be used for the count and the final result to prevent overflow.

1class Solution {2    public long countSubstrings(String s, char c) {3        long countOfC = 0;4        for (char ch : s.toCharArray()) {5            if (ch == c) {6                countOfC++;7            }8        }9        // The number of substrings is the sum of 1 + 2 + ... + countOfC10        // which is the formula for the k-th triangular number: k * (k + 1) / 211        return countOfC * (countOfC + 1) / 2;12    }13}