Given a binary string S of length N, the task is to find the length of the longest sub-sequence in it which is divisible by 3. Leading zeros in the sub-sequences are allowed.
Examples:
Input: S = “1001”
Output: 4
The longest sub-sequence divisible by 3 is “1001”.
1001 = 9 which is divisible by 3.
Input: S = “1011”
Output: 3 776
Naive approach: Generate all the possible sub-sequences and check if they are divisible by 3. The time complexity for this will be O((2N) * N).
Implementation:
C++
#include <bits/stdc++.h>using namespace std;bool isDivisibleBy3(string s) { int n = s.length(); int num = 0; for (int i = 0; i < n; i++) { num = num * 2 + (s[i] - '0'); } return (num % 3 == 0);}int longest(string s) { int n = s.length(); int maxLen = 0; for (int i = 0; i < (1 << n); i++) { string sub = ""; for (int j = 0; j < n; j++) { if ((i >> j) & 1) { sub.push_back(s[j]); } } if (isDivisibleBy3(sub)) { maxLen = max(maxLen, (int) sub.length()); } } return maxLen;}int main() { string s1 = "101"; cout <<longest(s1)<<endl; return 0;} |
Output:
2
Time Complexity: O((2^N) * N), N is the length of the binary string.
Auxiliary Space: O(1),as we are not using any extra space.
Efficient approach: Dynamic programming can be used to solve this problem. Let’s look at the states of DP.
DP[i][r] will store the longest sub-sequence of the substring S[i…N-1] such that it gives a remainder of (3 – r) % 3 when divided by 3.
Let’s write the recurrence relation now.
DP[i][r] = max(1 + DP[i + 1][(r * 2 + s[i]) % 3], DP[i + 1][r])
The recurrence is derived because of the following two choices:
- Include the current index i in the sub-sequence. Thus, the r will be updated as r = (r * 2 + s[i]) % 3.
- Don’t include the current index in the sub-sequence.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100int dp[N][3];bool v[N][3];// Function to return the length of the// largest sub-string divisible by 3int findLargestString(string& s, int i, int r){ // Base-case if (i == s.size()) { if (r == 0) return 0; else return INT_MIN; } // If the state has been solved // before then return its value if (v[i][r]) return dp[i][r]; // Marking the state as solved v[i][r] = 1; // Recurrence relation dp[i][r] = max(1 + findLargestString(s, i + 1, (r * 2 + (s[i] - '0')) % 3), findLargestString(s, i + 1, r)); return dp[i][r];}// Driver codeint main(){ string s = "101"; cout << findLargestString(s, 0, 0); return 0;} |
Java
// Java implementation of the approach class GFG { final static int N = 100 ; final static int INT_MIN = Integer.MIN_VALUE; static int dp[][] = new int[N][3]; static int v[][] = new int[N][3]; // Function to return the length of the // largest sub-string divisible by 3 static int findLargestString(String s, int i, int r) { // Base-case if (i == s.length()) { if (r == 0) return 0; else return INT_MIN; } // If the state has been solved // before then return its value if (v[i][r] == 1) return dp[i][r]; // Marking the state as solved v[i][r] = 1; // Recurrence relation dp[i][r] = Math.max(1 + findLargestString(s, i + 1, (r * 2 + (s.charAt(i) - '0')) % 3), findLargestString(s, i + 1, r)); return dp[i][r]; } // Driver code public static void main (String[] args) { String s = "101"; System.out.print(findLargestString(s, 0, 0)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach import numpy as npimport sysN = 100INT_MIN = -(sys.maxsize - 1)dp = np.zeros((N, 3)); v = np.zeros((N, 3)); # Function to return the length of the # largest sub-string divisible by 3 def findLargestString(s, i, r) : # Base-case if (i == len(s)) : if (r == 0) : return 0; else : return INT_MIN; # If the state has been solved # before then return its value if (v[i][r]) : return dp[i][r]; # Marking the state as solved v[i][r] = 1; # Recurrence relation dp[i][r] = max(1 + findLargestString(s, i + 1, (r * 2 + (ord(s[i]) - ord('0'))) % 3), findLargestString(s, i + 1, r)); return dp[i][r]; # Driver code if __name__ == "__main__" : s = "101"; print(findLargestString(s, 0, 0)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG { readonly static int N = 100 ; readonly static int INT_MIN = int.MinValue; static int [,]dp = new int[N, 3]; static int [,]v = new int[N, 3]; // Function to return the length of the // largest sub-string divisible by 3 static int findLargestString(String s, int i, int r) { // Base-case if (i == s.Length) { if (r == 0) return 0; else return INT_MIN; } // If the state has been solved // before then return its value if (v[i, r] == 1) return dp[i, r]; // Marking the state as solved v[i, r] = 1; // Recurrence relation dp[i, r] = Math.Max(1 + findLargestString(s, i + 1, (r * 2 + (s[i] - '0')) % 3), findLargestString(s, i + 1, r)); return dp[i, r]; } // Driver code public static void Main(String[] args) { String s = "101"; Console.Write(findLargestString(s, 0, 0)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar N = 100var dp = Array.from(Array(N), ()=>Array(3));var v = Array.from(Array(N), ()=>Array(3));// Function to return the length of the// largest sub-string divisible by 3function findLargestString(s, i, r){ // Base-case if (i == s.length) { if (r == 0) return 0; else return -1000000000; } // If the state has been solved // before then return its value if (v[i][r]) return dp[i][r]; // Marking the state as solved v[i][r] = 1; // Recurrence relation dp[i][r] = Math.max(1 + findLargestString(s, i + 1, (r * 2 + (s[i].charCodeAt(0) - '0'.charCodeAt(0))) % 3), findLargestString(s, i + 1, r)); return dp[i][r];}// Driver codevar s = "101";document.write( findLargestString(s, 0, 0));// This code is contributed by noob2000.</script> |
Output
2
Time Complexity: O(n)
Auxiliary Space: O(n * 3) ⇒ O(n), where n is the length of the given string.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
