Android-এ অ্যানাগ্রাম চেক এবং অ্যানাগ্রাম সংখ্যা গণনা

অ্যানাগ্রাম চেক এবং সাবস্ট্রিং-এ অ্যানাগ্রাম গণনা

এই উদাহরণে দুটি কাজ করা হয়েছে: ১) দুটি স্ট্রিং অ্যানাগ্রাম কিনা চেক, ২) প্রথম স্ট্রিং-এ দ্বিতীয় স্ট্রিং-এর অ্যানাগ্রাম কতবার আসে তা গণনা।

লেআউট (activity_main.xml)

<LinearLayout xmlns:android="https://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical"
    android:gravity="center"
    android:padding="16dp">

    <EditText android:id="@+id/edit_query" android:layout_width="match_parent"
        android:layout_height="wrap_content" android:hint="মূল স্ট্রিং (Text)" />
    <EditText android:id="@+id/edit_query1" android:layout_width="match_parent"
        android:layout_height="wrap_content" android:hint="প্যাটার্ন (Pattern)" android:layout_marginTop="16dp"/>
    <Button android:id="@+id/buttonPanel" android:layout_width="wrap_content"
        android:layout_height="wrap_content" android:text="গণনা করুন" android:layout_marginTop="24dp"
        android:layout_gravity="center" />

</LinearLayout>

MainActivity.java

package com.example.myapplication;

import android.os.Bundle;
import android.view.View;
import android.widget.EditText;
import android.widget.Toast;
import androidx.appcompat.app.AppCompatActivity;

public class MainActivity extends AppCompatActivity {

    EditText editText, editPattern;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        editText = findViewById(R.id.edit_query);
        editPattern = findViewById(R.id.edit_query1);

        findViewById(R.id.buttonPanel).setOnClickListener(v -> {
            String text = editText.getText().toString().trim().toLowerCase().replaceAll("\\s+", "");
            String pattern = editPattern.getText().toString().trim().toLowerCase().replaceAll("\\s+", "");

            if (text.isEmpty() || pattern.isEmpty()) {
                Toast.makeText(this, "দুই ফিল্ড পূরণ করুন", Toast.LENGTH_SHORT).show();
                return;
            }

            if (areAnagrams(text, pattern)) {
                int count = countAnagramOccurrences(text, pattern);
                Toast.makeText(this, "অ্যানাগ্রাম পাওয়া গেল: " + count + " বার", Toast.LENGTH_LONG).show();
            } else {
                Toast.makeText(this, "প্যাটার্নটি মূল স্ট্রিং-এর অ্যানাগ্রাম নয়", Toast.LENGTH_LONG).show();
            }
        });
    }

    // স্লাইডিং উইন্ডো + ক্যারেক্টার কাউন্ট ব্যবহার করে O(n) সময়ে অ্যানাগ্রাম গণনা
    private int countAnagramOccurrences(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        if (m > n) return 0;

        int[] patternCount = new int[26];
        int[] windowCount = new int[26];

        for (char c : pattern.toCharArray()) {
            if (c >= 'a' && c <= 'z') patternCount[c - 'a']++;
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            char c = text.charAt(i);
            if (c >= 'a' && c <= 'z') windowCount[c - 'a']++;

            // উইন্ডো সাইজ বড় হলে বাম পাশের ক্যারেক্টার বাদ দিন
            if (i >= m) {
                char leftChar = text.charAt(i - m);
                if (leftChar >= 'a' && leftChar <= 'z') windowCount[leftChar - 'a']--;
            }

            // উইন্ডো সাইজ মেললে তুলনা করুন
            if (i >= m - 1 && java.util.Arrays.equals(patternCount, windowCount)) {
                result++;
            }
        }
        return result;
    }

    private boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            if (c1 >= 'a' && c1 <= 'z') count[c1 - 'a']++;
            if (c2 >= 'a' && c2 <= 'z') count[c2 - 'a']--;
        }
        for (int c : count) if (c != 0) return false;
        return true;
    }
}

অ্যালগরিদম: স্লাইডিং উইন্ডো (Sliding Window)

1. প্যাটার্নের ক্যারেক্টার ফ্রিকোয়েন্সি গণনা করুন
2. টেক্সটের উপর একটি ফিক্সড সাইজ উইন্ডো (pattern.length()) স্লাইড করান
3. প্রতিটি উইন্ডোর ক্যারেক্টার কাউন্ট প্যাটার্নের সাথে মিলিয়ে নিন
4. মেললে কাউন্ট বাড়ান
5. টাইম কমপ্লেক্সিটি: O(n), স্পেস: O(1) [-fixed 26 array]

উদাহরণ

• Text: "forxxorfxdofr"
• Pattern: "for"
• অ্যানাগ্রাম সাবস্ট্রিং: "for", "orf", "ofr", "rfo", "for" = ৫টি