- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have two non-empty strings s and t that are of the same length. We have to partition them into substrings such that each pair of s and t substring is the same size and they are the anagrams of each other. Now find the cut indexes such that it results in the maximum number of cuts of s and t. If no result is found, then return empty list.

So, if the input is like s = "bowcattiger" t = "owbactietgr", then the output will be [0, 3, 5, 6, 10], as we can partition the string into 5 partitions such that each string is an anagram of each other. s = ["bow", "ca", "t", "tige", "r"], t = ["owb", "ac", "t", "ietg", "r"]

To solve this, we will follow these steps −

- intervals := a new list
- cs := a map with character present in s and its frequency
- ct := a map with character present in t and its frequency
- if cs is not same as ct, then
- return a new list

- for x in range size of s - 1 down to 0, do
- cs[s[x]] := cs[s[x]] - 1
- ct[t[x]] := ct[t[x]] - 1
- if cs is same as ct, then
- insert x at the end of intervals

- sort the list intervals and return

Let us see the following implementation to get better understanding −

from collections import Counter class Solution: def solve(self, a, b): intervals = [] ca = Counter(a) cb = Counter(b) if ca != cb: return [] for x in reversed(range(len(a))): ca[a[x]] -= 1 cb[b[x]] -= 1 if ca == cb: intervals.append(x) return sorted(intervals) ob = Solution() s = "bowcattiger" t = "owbactietgr" print(ob.solve(s, t))

"bowcattiger", "owbactietgr"

[0, 3, 5, 6, 10]

- Related Questions & Answers
- C++ Program to Find number of Ways to Partition a word such that each word is a Palindrome
- Program to partition color list in Python
- String partition() in Python
- Partition problem
- Check whether two strings are anagram of each other in Python
- Array Partition I in Python
- Program to find partition array into disjoint intervals in Python
- Partition List in C++
- Partition Labels in C++
- C++ Partition a Number into Two Divisible Parts
- Partition Array for Maximum Sum in Python
- Check if two strings are anagram of each other using C++
- Program to find size of each partition of a list where each letter appears at most one piece in Python
- Equal Tree Partition in C++
- Partition Equal Subset Sum in C++

Advertisements