{"id":1845,"date":"2024-02-04T13:00:00","date_gmt":"2024-02-04T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1845"},"modified":"2024-03-06T10:13:23","modified_gmt":"2024-03-06T10:13:23","slug":"permutation-in-string","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/permutation-in-string\/","title":{"rendered":"Permutation in String Problem (C++, Java, Python)"},"content":{"rendered":"\n

One of the fun leetcode problems is related to Permutation in String. You can solve it using various methods like backtracking<\/a>, and recursion<\/a>, which we will learn how to do right here.<\/p>\n\n\n\n

Permutation in String problem<\/strong><\/h2>\n\n\n\n

A permutation is a set of all the possible values which is formed by rearranging the given value. For example, permutations of 123 are 123, 132, 213, 231, 312, and 321. In all the permutations, the frequency of each element should remain the same as in the given value. <\/p>\n\n\n

\n
\"Example<\/figure>\n<\/div>\n\n\n

In the Permutation in String problem, you have given two strings. String \u2018A\u2019 and string \u2018B\u2019. You have to find whether any permutation of string A lies in string B. If it is returned true, if not, return false.<\/strong><\/p>\n\n\n\n

Here is an example:<\/p>\n\n\n\n

Input<\/strong>:     A<\/strong>: ab<\/p>\n\n\n\n

                B: <\/strong>cdbaha<\/p>\n\n\n\n

Output<\/strong>:   True <\/p>\n\n\n\n

Explanation: <\/strong>Permutations of ab are ab <\/strong>and ba. <\/strong>In \u201ccdba<\/strong>ha\u201d\u00a0 ba lies inside it. This means the permutation of a is a substring of string B.<\/p>\n\n\n\n

The naive solution is to find out all the permutations of string A and then check if any of the strings is a substring of B. If it is returned true. If not return false.<\/p>\n\n\n\n

Let\u2019s examine this approach step by step:<\/p>\n\n\n\n

    \n
  1. First, find all the permutations of the string. You can find this by backtracking.<\/li>\n\n\n\n
  2. After finding all the permutations go to each permutation and check if it lies inside string B or not. You can find this by sliding the window approach. In this approach, you have to take a substring starting from 0 and of size the same as A and then keep on adding the next index value and removing the previous index values.\u00a0<\/li>\n\n\n\n
  3. If you find any substring in B same as the permutation of string A return true.<\/li>\n\n\n\n
  4. If not, return false.<\/li>\n<\/ol>\n\n\n\n
    \"Explanation<\/figure>\n\n\n\n

    The time complexity of the above solution is O((n*n!) + (k*n!)) where n is the size of string A and k is the size of string B. As we are calculating the permutation of string A whose time complexity is O(n*n!) and for finding whether the permutation lies in string B or not it took O(k*n!) time complexity so overall time complexity is O((n*n!) + (k*n!)).\u00a0<\/p>\n\n\n\n

    The space complexity is O(n!) as there are total n!. A permutation is possible for string A.<\/p>\n\n\n\n

    Optimized Approach<\/strong><\/h2>\n\n\n\n

    In the above approach, we find all permutations of a string, which leads to a significant increase in time complexity. Instead of finding the permutations of the string, we can utilize the properties of permutations.<\/p>\n\n\n\n

    In a permutation, the frequency of each element remains the same across all permutations. Therefore, we store the frequency of each element in an array and check in string B whether any substring has the same frequency or not. <\/strong>If the frequencies match, we return true; otherwise, we return false.<\/p>\n\n\n\n

    Let\u2019s learn how to do it:<\/p>\n\n\n\n

      \n
    1. First, check if the size of A is greater than B and return false. <\/li>\n\n\n\n
    2. First, create an array arr, of size 26 which stores the frequency of each character in string A.<\/li>\n\n\n\n
    3. Store the frequency of each element in string A.<\/li>\n\n\n\n
    4. Create another array of size 26 and name this array a temp array. Now run a loop of size n (n is the size of string A) and store the frequency of each character in string B till size n.<\/li>\n\n\n\n
    5. Check if the temp array is the same as arr. If it is returned true.<\/li>\n\n\n\n
    6.  If not check for the next n elements in string B by sliding window approach and check at any point temp become equal to array arr return true. <\/li>\n\n\n\n
    7. At last return false.<\/li>\n<\/ol>\n\n\n\n

      Now is the time to code it.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Here is the C++ solution for Permutation in String problem:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\nusing namespace std;\n\nbool check_permutation(string A, string B){\n        vector<int>v(26,0);\n        vector<int>temp(26,0);\n        \/\/ if s1 length is greater than s2\n        int k=A.size();\n        if(k>B.size()) return false;\n\n        for(int i=0;i<k;i++) {\n            v[A[i]-'a']++;\n        }\n\n        for(int i=0;i<k;i++){\n            temp[B[i]-'a']++;\n        }\n\n        if(temp==v) return true;\n\n        int ind=1;\n        for(int i=ind;i+k<=B.size();i++){\n            temp[B[i-1]-'a']--;\n            temp[B[i+k-1]-'a']++;\n            if(temp==v) return true;\n        }\n\n        return false;\n}\n\nint main(){\n\n    string A = "otut";\n    string B = "favtutor";\n\n    bool ans = check_permutation(A, B);\n    ans? cout<<"True"<<endl: cout<<"False"<<endl;\n    return 0;\n}<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      We can implement the approach in Java as well:<\/p>\n\n\n\n
      import java.util.Arrays;\n\npublic class Main {\n    \n    static boolean checkPermutation(String A, String B) {\n        int[] v = new int[26];\n        int[] temp = new int[26];\n        \/\/ if s1 length is greater than s2\n        int k = A.length();\n        if (k > B.length()) return false;\n\n        for (int i = 0; i < k; i++) {\n            v[A.charAt(i) - 'a']++;\n        }\n\n        for (int i = 0; i < k; i++) {\n            temp[B.charAt(i) - 'a']++;\n        }\n\n        if (Arrays.equals(temp, v)) return true;\n\n        for (int i = 1; i + k <= B.length(); i++) {\n            temp[B.charAt(i - 1) - 'a']--;\n            temp[B.charAt(i + k - 1) - 'a']++;\n            if (Arrays.equals(temp, v)) return true;\n        }\n\n        return false;\n    }\n\n    public static void main(String[] args) {\n        String A = "otut";\n        String B = "favtutor";\n\n        boolean ans = checkPermutation(A, B);\n        System.out.println(ans ? "True" : "False");\n    }\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      Here is the Python program for Permutation in String problem:<\/p>\n\n\n\n
      def check_permutation(A, B):\n    v = [0] * 26\n    temp = [0] * 26\n    # if s1 length is greater than s2\n    k = len(A)\n    if k > len(B):\n        return False\n\n    for i in range(k):\n        v[ord(A[i]) - ord('a')] += 1\n\n    for i in range(k):\n        temp[ord(B[i]) - ord('a')] += 1\n\n    if temp == v:\n        return True\n\n    ind = 1\n    for i in range(ind, len(B) - k + 1):\n        temp[ord(B[i - 1]) - ord('a')] -= 1\n        temp[ord(B[i + k - 1]) - ord('a')] += 1\n        if temp == v:\n            return True\n\n    return False\n\n\nif __name__ == "__main__":\n    A = "otut"\n    B = "favtutor"\n\n    ans = check_permutation(A, B)\n    print("True" if ans else "False")<\/pre><\/div>\n\n\n\n
      Output:<\/strong> <\/p>\n\n\n\n
      True<\/code><\/pre>\n\n\n\n
      The time complexity to solve the Permutation in a String is O(n + k), where n is the size of string A and k is the size of string B. This is because we are running a loop to store the frequency of all elements in the string A whose time complexity is O(n). After that, we check every substring of size n has the same frequency as of array arr, which takes O(k) time complexity.\u00a0<\/p>\n\n\n\n
      The space complexity is O(26) ~ O(1), As we are just storing the frequency of each character.<\/p>\n\n\n\n
      Here is the comparison that shows how the optimized approach is better:<\/p>\n\n\n\n
       Approach<\/strong><\/th>Time Complexity<\/strong><\/th>Space Complexity<\/strong><\/th> Description<\/strong><\/th><\/tr><\/thead>
      Brute Force<\/td>O((n* n!) +(k*n!))<\/td>O(n!)<\/td>We are finding all the permutations which laid our time complexity to O(n*n!)<\/td><\/tr>
      Optimized Approach<\/td>O(n + k)     n: the size of A     k: the size of B<\/td>O(n!)<\/td>We are using the array to store the frequency of each element in string A.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      We have seen various approaches to solve the Permutation in String problem from leetcode<\/a>. The storing frequency approach saved our time complexity to a large extent. You can now solve other questions based on the Sliding window approach<\/a>, Valid Anagram<\/a>, etc.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Find out how to solve the Permutation in String problem from leetcode with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":1847,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1845","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1845","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1845"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1845\/revisions"}],"predecessor-version":[{"id":2207,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1845\/revisions\/2207"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1847"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1845"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1845"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1845"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}