DSA Day 5/100

Topic: Strings

Questions Attempted: 2

1	Binary String
2	Palindrome Check

Questions Successfully Completed: 2

Binary String

Time Complexity : O(n^2)

Space Complexity : O(n)

 public static int binarySubstring(int a, String str)
    // Time Complexity : O(N^2) 
    {
        char[] ch1 = str.toCharArray();
        int count =0;

        for(int i=0;i<ch1.length-1;i++){
                    if(ch1[i]=='1'){
                        for(int j=i+1;j<ch1.length;j++){
                            if(ch1[j]=='1'){
                                count++;
                            }
                        }
                    }
        }
        return count;
    }

Time Complexity : O(n)

Question

Given a binary string S. The task is to count the number of substrings that start and end with 1. For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.

// Time Complexity : O(N)
    {
        char[] ch = str.toCharArray();
        int count = 0;

        for(int i=0;i<a;i++){
            if(ch[i]=='1'){
                count++;
            }
        }
        return (count*(count-1))/2;
    }

}

Palindrome Check

Time Complexity : O(n)

Space Complexity : O(1)

Question

"ABBA" -> EVEN LENGTH "ACAFACA" -> ODD LENGTH

public static boolean pallind(String str){
        // convert immutable string to mutable character array
        char[] ch1 = str.toCharArray();
        int beg = 0;
        int end = str.length()-1;

        while(beg<end){
            if(ch1[beg]!=ch1[end]){
                return false;
            }
            beg++;
            end--;
        }
        return true;
    }
    public static void main(String[] args) {
        String str1 = "ABBA";
        String str2 = "ACAFACA";
        String str3 = "DDCCFF";
        System.out.println(pallind(str1));
        System.out.println(pallind(str2));
        System.out.println(pallind(str3));
    }

Thank you for Reading :)