Given a string S. Let k be the maximum number of partitions possible of the given string with each partition starts with a distinct letter. The task is to find the number of ways string S can be split into k partition (non-empty) such that each partition starts with a distinct letter. Print number modulo 1000000007.
Note : S consists of lowercase letters only.
 
Example 1:
Input:
S = "abb"
Output:
2
Explanation:
 "abb" can be maximum split into 2 partitions
{a, bb} with distinct starting letter, for k = 2.
And, the number of ways to split "abb"
into 2 partitions with distinct starting letter
are 2 {a, bb} and {ab, b}.
Example 2:
Input:
S = "abbcc"
Output:
4
Explanation:
"abbcc" can be maximum split into 3 partitions
with distinct letter, so k=3. Thus the number
of ways to split "abbcc" into 3 partitions with
distinct letter is 4 i.e. {ab, b, cc},
{ab, bc, c},{a, bb, cc} and {a, bbc, c}. 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function waysToSplit() which takes a String S and returns the answer.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|1|)
 
Constraints:
1 <= |S| <=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def waysToSplit(self, S):

        # code here

Solutions:
class Solution:

	def waysToSplit(self, S):
		lookup = {}
		for i in S:
			lookup[i] = 1 + lookup.get(i, 0)
		lookup[S[0]] = 1
		res = 1
		for i in lookup.keys():
			res *= lookup[i]
		return res % 1000000007


from collections import defaultdict

class Solution:

	def waysToSplit(self, S):
		store = defaultdict(lambda : 0)
		for item in S:
			store[item] += 1
		store[S[0]] = 1
		output = 1
		for item in store.values():
			output *= item
		return output % (10 ** 9 + 7)


class Solution:

	def waysToSplit(self, S):
		d = {}
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		d[S[0]] = 1
		res = 1
		for i in d:
			res *= d[i]
		return res % 1000000007


class Solution:

	def waysToSplit(self, S):
		d = {}
		start = S[0]
		for i in S:
			if i != start:
				if i not in d:
					d[i] = 1
				else:
					d[i] += 1
		prod = 1
		for i in d:
			prod *= d[i]
		return prod % 1000000007


class Solution:

	def waysToSplit(self, S):
		h = [0] * 26
		for c in S:
			h[ord(c) - ord('a')] += 1
		ans = 1
		mod = 10 ** 9 + 7
		h[ord(S[0]) - ord('a')] = 1
		for e in h:
			if e != 0:
				ans *= e
		return ans % mod


class Solution:

	def waysToSplit(self, S):
		dic = {}
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		ans = 1
		for i in dic:
			if i != S[0]:
				ans = ans * dic[i]
		return ans % 1000000007