CODEWITHSUNDEEP
c++stringsubstring
Scott
Scott

Reputation: 77

How do I efficiently find the number of substrings in a string with same first and last characters?

I'm trying to find the number of substrings in a string with same first and last characters.

I could solve it in the naive way by taking two for loops.

I feel that it can be solved much more efficiently.

How do I solve it in a more efficient way?

Upvotes: 0

Views: 164

Answers (1)

SU3
SU3

Reputation: 5409

Loop over the string, and count the number of occurrences for each distinct character. Then, if a character occurs only once, there are no substrings ending and beginning with it, if it occurs twice -- there's only 1, if 3 times -- there are 3, if 4 times -- 6. The function is C(n,2) = n!/(2!(n-2)!) = n(n-1)/2.

Here's a potential implementation.

inline int Nchoose2(int n) {
  return n*(n-1)/2;
}

std::string s;
std::map<char,int> m;
int cnt = 0;

for (char c : s) {
  if (!m.count(c)) m[c] = 0;
  else ++m[c];
}

for (auto &c : m)
   cnt += Nchoose2(c.second);

Upvotes: 4

Related Questions