Find the numbers of strings that can be formed after processing Q queries | Java program to implement above approach ; To store the size of string and number of queries ; To store parent and rank of ith place ; To store maximum interval ; Function for initialization ; Function to find parent ; Function to make union ; Power function to calculate a raised to m1 under modulo 10000007 ; Function to take maxmium interval ; Function to find different possible strings ; make union of all chracters which are meant to be same ; find number of different sets formed ; return the required answer ; Driver Code ; queries
import java . util . * ; class GFG { static final int N = 2005 ; static final int mod = 1000000007 ; static int n , q ; static int [ ] par = new int [ N ] , Rank = new int [ N ] ; static HashMap < Integer , Integer > m = new HashMap < > ( ) ; static void initialize ( ) { for ( int i = 0 ; i <= n ; i ++ ) { par [ i ] = i ; Rank [ i ] = 0 ; } } static int find ( int x ) { if ( par [ x ] != x ) par [ x ] = find ( par [ x ] ) ; return par [ x ] ; } static void Union ( int x , int y ) { int xpar = find ( x ) ; int ypar = find ( y ) ; if ( Rank [ xpar ] < Rank [ ypar ] ) par [ xpar ] = ypar ; else if ( Rank [ xpar ] > Rank [ ypar ] ) par [ ypar ] = xpar ; else { par [ ypar ] = xpar ; Rank [ xpar ] ++ ; } } static long power ( long a , long m1 ) { if ( m1 == 0 ) return 1 ; else if ( m1 == 1 ) return a ; else if ( m1 == 2 ) return ( 1L * a * a ) % mod ; else if ( m1 % 2 == 1 ) return ( 1L * a * power ( power ( a , m1 / 2 ) , 2 ) ) % mod ; else return power ( power ( a , m1 / 2 ) , 2 ) % mod ; } static void query ( int l , int r ) { if ( m . containsKey ( l + r ) ) m . put ( l + r , Math . max ( m . get ( l + r ) , r ) ) ; else m . put ( l + r , r ) ; } static long possiblestrings ( ) { initialize ( ) ; for ( Integer i : m . keySet ( ) ) { int x = i - m . get ( i ) ; int y = m . get ( i ) ; while ( x < y ) { Union ( x , y ) ; x ++ ; y -- ; } } int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) if ( par [ i ] == i ) ans ++ ; return power ( 26 , ans ) % mod ; } public static void main ( String [ ] args ) { n = 4 ; query ( 1 , 3 ) ; query ( 2 , 4 ) ; System . out . println ( possiblestrings ( ) ) ; } }