Given a string S of length N containing only lowercase alphabets. You are also given a permutation P of length N containing integers from 0 to N-1. In (i+1)'th day you can take the P[i] value of the permutation array and replace S[P[i]] with a '?'.
For example in day 1, we can choose index of permutation array is i=0 and replace S[P[0]] with '?'.
Similarly in day 2, we can choose index of permutation array is i=1. You can replace S[P[1]] with '?'.
Similarly in day 3,we can choose index of permutation array is i=2. You can replace S[P[2]] with '?'.
You have to tell the minimum number of days required, such that after it for all index i (0<=i<N-1), if S[i]!='?', then S[i]!=S[i+1].
Example 1:
Input:
N = 4
S = "aabb"
P[] = {2, 1, 3, 0}
Output: 2
Explanation: In day 1, we replace S[P[0]] with '?'. 
After that String S = "aa?b". As we can see S 
still has character 'a' at index 0 and 1.
In day 2, we replace S[P[1]] with '?'. After 
that String S = "a??b". As we can see the String 
has for all index i (0<=i<N-1), if S[i]!='?', then S[i]!=S[i+1].
Example 2:
Input:
N = 4
S = "abca"
P[] = {3, 0, 2, 1}
Output: 0
Explanation: We can see that the initial string 
S = "abca" has for all index i (0<=i<N-1), if S[i]!='?', then S[i]!=S[i+1].
Your Task: 
You don't need to read input or print anything. Your task is to complete the function getMinimumDays() which takes the string S, array P[] and its size N as input parameters and returns the minimum number of days required such that string satisfies with the condition given earlier.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{5}
0 <= P[i] <= N-1
S contains only lowercase alphabets.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Combinatorics

Data structures

Starter code: from typing import List





class Solution:

    def getMinimumDays(self, N : int, S : str, P : List[int]) -> int:

        # code here

        





Solutions:
from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		h = [False] * N
		ans = 0
		c = 0
		for i in range(N - 1):
			h[i] = S[i] == S[i + 1]
			c += S[i] == S[i + 1]
		for j in P:
			if c <= 0:
				return ans
			ans += 1
			c -= h[j]
			h[j] = 0
			if j:
				c -= h[j - 1]
				h[j - 1] = 0
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, s: str, P: List[int]) -> int:
		ans = 0
		s = list(s)
		for i in range(N):
			chr_index = P[i]
			if chr_index < N - 1 and s[chr_index + 1] == s[chr_index] or (chr_index > 0 and s[chr_index] == s[chr_index - 1]):
				s[chr_index] = '?'
				ans = chr_index = i + 1
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		day = 0
		S = list(S)
		for i in range(N - 1):
			if S[i] == S[i + 1] and S[i] != '?':
				for index in range(len(P)):
					if day >= N:
						break
					S[P[day]] = '?'
					day += 1
					if S[i] == S[i + 1] and S[i] != '?':
						continue
					else:
						break
		return day


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		hsh = [False] * N
		ans = 0
		cnt = 0
		for i in range(N - 1):
			hsh[i] = S[i] == S[i + 1]
			cnt += S[i] == S[i + 1]
		for it in P:
			if cnt <= 0:
				return ans
			ans += 1
			cnt -= hsh[it]
			hsh[it] = 0
			if it:
				cnt -= hsh[it - 1]
				hsh[it - 1] = 0
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		S = list(S)
		day = 0
		for i in range(N - 1):
			if S[i] != '?' and S[i] == S[i + 1]:
				while S[i] == S[i + 1]:
					S[P[day]] = '?'
					day += 1
		return day


from typing import List

class Solution:

	def getMinimumDays(self, n: int, s: str, p: List[int]) -> int:
		s = list(s)
		day = 0
		for i in range(n - 1):
			if s[i] != '?' and s[i] == s[i + 1]:
				while s[i] == s[i + 1]:
					s[p[day]] = '?'
					day += 1
		return day


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		c = 0
		S = list(S)
		for i in range(N - 1):
			if S[i] == S[i + 1]:
				c += 1
		if c == 0:
			return 0
		for i in range(len(P)):
			index = P[i]
			if index - 1 >= 0 and S[index - 1] == S[index]:
				c -= 1
				if c == 0:
					return i + 1
			if index + 1 <= len(S) - 1 and S[index + 1] == S[index]:
				c -= 1
				if c == 0:
					return i + 1
			S[index] = '?'
			if c == 0:
				return i + 1
		return -1


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		ans = 0
		S = list(S)
		i = 0
		while i < N - 1:
			if P[i] + 1 != N and S[P[i]] == S[P[i] + 1] or (P[i] != 0 and S[P[i]] == S[P[i] - 1]):
				S[P[i]] = '?'
				ans = i + 1
			i += 1
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		repeats = set()
		for i in range(N - 1):
			if S[i] == S[i + 1]:
				repeats.add(i)
		i = 0
		while repeats:
			repeats.difference_update({P[i], P[i] - 1})
			i += 1
		return i


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		S = list(S)
		day = 1
		i = 0
		count = 0
		while i < N - 1:
			if S[i] != S[i + 1]:
				i += 1
			elif S[i] == '?' and S[i + 1] == '?':
				i += 1
			else:
				S[P[day - 1]] = '?'
				day += 1
				count += 1
		return count


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		i = 0
		x = 0
		cnt = 0
		S = list(S)
		while i < len(S) - 1:
			if S[i] == S[i + 1]:
				x += 1
			i += 1
		if x == 0:
			return 0
		for i in range(N):
			if P[i] == 0:
				if S[0] == S[1]:
					cnt += 1
			elif P[i] == N - 1:
				if S[N - 1] == S[N - 2]:
					cnt += 1
			elif S[P[i]] == S[P[i] - 1] and S[P[i]] == S[P[i] + 1]:
				cnt += 2
			elif S[P[i]] == S[P[i] - 1] or S[P[i]] == S[P[i] + 1]:
				cnt += 1
			S[P[i]] = '?'
			if cnt == x:
				return i + 1


class Solution:

	def getMinimumDays(self, n, s, p):
		s = list(s)
		day = 0
		for i in range(n - 1):
			if s[i] != '?' and s[i] == s[i + 1]:
				while s[i] == s[i + 1]:
					s[p[day]] = '?'
					day += 1
		return day


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		S = [*S]
		count = 0
		for i in range(N - 1):
			count += S[i] == S[i + 1]
		i = 0
		while count > 0:
			if P[i] == 0:
				count -= S[0] == S[1]
			elif P[i] == N - 1:
				count -= S[-1] == S[-2]
			else:
				count -= S[P[i]] == S[P[i] + 1]
				count -= S[P[i]] == S[P[i] - 1]
			S[P[i]] = i
			i += 1
		return i


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		li = [int(i < N - 1 and S[i] == S[i + 1]) for i in range(N)]
		c = len([i for i in li if i])
		days = 0
		for x in P:
			if c == 0:
				break
			if li[x]:
				c -= 1
			li[x] = 0
			if x - 1 >= 0:
				if li[x - 1]:
					c -= 1
					li[x - 1] = 0
			days += 1
		return days


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		l = []
		for v in S:
			l.append(v)
		count = 0
		for idx in range(N - 1):
			if S[idx] == S[idx + 1]:
				count += 1
		pdx = 0
		p = len(P)
		while count != 0 and pdx < p:
			idx = P[pdx]
			if idx < N - 1 and l[idx] == l[idx + 1]:
				count -= 1
			if idx > 0 and l[idx] == l[idx - 1]:
				count -= 1
			l[idx] = '?'
			pdx += 1
		return pdx


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		k = 0
		s = 0
		S = list(S)
		while k < N - 1:
			if P[k] + 1 != N and S[P[k]] == S[P[k] + 1] or (P[k] != 0 and S[P[k]] == S[P[k] - 1]):
				S[P[k]] = '?'
				s = k + 1
			k += 1
		return s


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		if N == 1:
			return 0
		s = set()
		left = 0
		right = 0
		for i in range(N - 1):
			if S[i] == S[i + 1]:
				right = right + 1
				continue
			elif left != right:
				for i in range(left, right + 1):
					if i == left:
						s.add((left, left + 1))
					elif i == right:
						s.add((right - 1, right))
					else:
						s.add((i, i + 1))
						s.add((i - 1, i))
				left = i + 1
				right = i + 1
			else:
				left = i + 1
				right = i + 1
		if right == N - 1 and left != right:
			for i in range(left, right + 1):
				if i == left:
					s.add((left, left + 1))
				elif i == right:
					s.add((right - 1, right))
				else:
					s.add((i, i + 1))
					s.add((i - 1, i))
		if len(s) == 0:
			return 0
		for i in range(N):
			temp = P[i]
			if temp == 0:
				s.discard((0, 1))
			elif temp == N - 1:
				s.discard((N - 2, N - 1))
			else:
				s.discard((temp, temp + 1))
				s.discard((temp - 1, temp))
			if len(s) == 0:
				return i + 1


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		c = 0
		i = 0
		j = 0
		l = [*S]
		while i < len(S) - 1 and j < len(P):
			if l[i] != '?' and l[i] == l[i + 1]:
				l[P[j]] = '?'
				c += 1
				j += 1
			else:
				i += 1
		return c


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		arr = [S[i] for i in range(N)]
		l = -1
		for i in range(N):
			if P[i] > 0:
				if arr[P[i]] == arr[P[i] - 1]:
					arr[P[i]] = '?'
					l = i
			if P[i] < N - 1:
				if arr[P[i]] == arr[P[i] + 1]:
					arr[P[i]] = '?'
					l = i
		return l + 1


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		ans = 0
		hmap = {}
		for i in range(N):
			hmap[P[i]] = i
		i = 0
		while i < N - 1:
			if S[i] == S[i + 1]:
				ans = max(ans, min(hmap[i], hmap[i + 1]) + 1)
				if hmap[i] < hmap[i + 1]:
					i += 1
				else:
					i += 2
			else:
				i += 1
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		S = [x for x in S]
		count = 0
		for i in range(N - 1):
			if S[i] == S[i + 1]:
				count += 1
		if count == 0:
			return 0
		ans = 0
		for i in range(N):
			tmp = P[i]
			if tmp > 0 and S[tmp] == S[tmp - 1]:
				count -= 1
			if tmp < N - 1 and S[tmp] == S[tmp + 1]:
				count -= 1
			S[tmp] = '?'
			ans += 1
			if not count:
				return ans
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		mn = {x: i for (i, x) in enumerate(P)}
		res = 0
		i = 0
		while i < N - 1:
			if S[i] == S[i + 1]:
				if mn[i] > mn[i + 1]:
					res = max(res, mn[i + 1] + 1)
					i += 1
				else:
					res = max(res, mn[i] + 1)
			i += 1
		return res


from typing import List

class Solution:

	def getMinimumDays(self, n: int, s: str, p: List[int]) -> int:
		m = -1
		for i in range(n):
			if p[i] == 0:
				if s[p[i]] == s[p[i] + 1] and s[p[i]] != '?':
					m = max(m, i + 1)
					s = '?' + s[1:]
			elif p[i] == n - 1:
				if s[p[i] - 1] == s[p[i]] and s[p[i]] != '?':
					m = max(m, i + 1)
					s = s[0:n - 1] + '?'
			elif (s[p[i]] == s[p[i] - 1] or s[p[i]] == s[p[i] + 1]) and s[p[i]] != '?':
				m = max(m, i + 1)
				s = s[0:p[i]] + '?' + s[p[i] + 1:]
		if m == -1:
			return 0
		else:
			return m


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, p: List[int]) -> int:
		S = list(S)
		c = 0
		mark = -1
		for j in range(N):
			i = P[j]
			if i == 0:
				if S[i] == S[i + 1]:
					S[i] = '?'
					mark = j
			elif i == N - 1:
				if S[i] == S[i - 1]:
					S[i] = '?'
					mark = j
			elif S[i] == S[i + 1] or S[i] == S[i - 1]:
				S[i] = '?'
				mark = j
		c = mark + 1
		return c


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		n = N
		s = S
		p = P
		ans = N
		a = list(s)
		for i in range(n):
			a[p[i]] = '?'
		for i in range(n - 1, -1, -1):
			a[p[i]] = s[p[i]]
			if p[i] != 0 and a[p[i]] == a[p[i] - 1] or (p[i] != n - 1 and a[p[i]] == a[p[i] + 1]):
				break
			ans -= 1
		return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		S_arr = []
		for i in range(len(S)):
			S_arr.append(S[i])
		i = 0
		j = 0
		while i < len(S_arr) - 1:
			if S_arr[i] == '?' or S_arr[i] != S_arr[i + 1]:
				i += 1
			else:
				index = P[j]
				S_arr[index] = '?'
				j += 1
		return j


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		sarr = list(S)
		days = 0
		newP = {}
		for i in range(N):
			newP[str(P[i])] = i
		i = 0
		days = [0]
		while i < N - 1:
			if sarr[i] == sarr[i + 1]:
				toReplace = min(newP[str(i)], newP[str(i + 1)])
				sarr[P[toReplace]] = '?'
				days.append(toReplace + 1)
			i += 1
		return max(days)


from typing import List

class Solution:

	def getMinimumDays(self, n: int, s: str, a: List[int]) -> int:
		c = 0
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				c += 1
		if c == 0:
			return 0
		(ans, s) = (0, list(s))
		for i in range(n):
			curr = a[i]
			if curr > 0 and s[curr] == s[curr - 1]:
				c -= 1
			if curr < n - 1 and s[curr] == s[curr + 1]:
				c -= 1
			s[curr] = '?'
			ans += 1
			if c == 0:
				return ans


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		x = []
		S = list(S)
		for i in range(N - 1):
			if S[i] == S[i + 1]:
				x.append(i)
		j = 0
		for i in range(len(x)):
			while S[x[i]] != '?' and S[x[i] + 1] != '?':
				S[P[j]] = '?'
				j += 1
		return j


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		tempString = list(S)
		temp = tempString[0]
		j = 0
		for i in range(N - 1):
			if tempString[i] == '?':
				continue
			if tempString[i + 1] == tempString[i]:
				while True:
					if i == P[j] or i + 1 == P[j]:
						tempString[i] = '?'
						break
					tempString[P[j]] = '?'
					j += 1
		if j == 0:
			return 0
		return j + 1


from typing import List

class Solution:

	def getMinimumDays(self, n: int, s: str, p: List[int]) -> int:
		s = list(s)
		pre = 0
		for i in range(n):
			if i >= 1:
				if s[i] == s[i - 1]:
					pre += 1
			if i + 1 < n:
				if s[i] == s[i + 1]:
					pre += 1
		if pre == 0:
			return 0
		for i in range(n):
			curr = p[i]
			if curr >= 1 and s[curr] == s[curr - 1]:
				pre -= 2
			if curr + 1 < n and s[curr] == s[curr + 1]:
				pre -= 2
			s[curr] = '?'
			if pre == 0:
				return i + 1
		return n


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		num_of_pairs = 0
		for (i, c) in enumerate(S):
			if i < N - 1 and S[i] == S[i + 1]:
				num_of_pairs += 1
		if num_of_pairs == 0:
			return 0
		num_of_steps = 0
		l = list(S)
		for i in range(N):
			num_of_steps += 1
			if P[i] < N - 1 and l[P[i]] == l[P[i] + 1]:
				num_of_pairs -= 1
			if P[i] > 0 and l[P[i] - 1] == l[P[i]]:
				num_of_pairs -= 1
			l[P[i]] = '?'
			if num_of_pairs <= 0:
				break
		return num_of_steps


from typing import List

class Solution:

	def getMinimumDays(self, n, ss, pp):
		ss = list(ss)
		c = 0
		for i in range(n - 1):
			if ss[i] == ss[i + 1]:
				c += 1
		if c == 0:
			return 0
		for i in range(n):
			now = pp[i]
			if now + 1 < n and ss[now] == ss[now + 1]:
				c -= 1
			if now - 1 >= 0 and ss[now - 1] == ss[now]:
				c -= 1
			ss[now] = '?'
			if c <= 0:
				return i + 1


from typing import List

class Solution:

	def getMinimumDays(self, N: int, S: str, P: List[int]) -> int:
		s = S
		p = P
		h = set()
		ans = N
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				h.add((i, i + 1))
		for i in range(len(p)):
			if len(h) == 0:
				ans = i
				break
			if (p[i], p[i] + 1) in h:
				h.remove((p[i], p[i] + 1))
			if (p[i] - 1, p[i]) in h:
				h.remove((p[i] - 1, p[i]))
		return i