Showing posts with label Algorithm. Show all posts

Saturday, 29 March 2025

adjacent_find() ফাংশনটি বাংলায় ব্যাখ্যা এবং সব ধরনের সম্ভাব্য উদাহরণ

on March 29, 2025 in adjacent_find(), Algorithm, array, begin, DSA, end, string, vector with No comments

C++ adjacent_find() ফাংশন - বাংলায় ব্যাখ্যা ও উদাহরণ

C++ এর adjacent_find() ফাংশন - বাংলায় ব্যাখ্যা

লেখক: Shakil Babu | তারিখ: ২৯ মার্চ, ২০২৫

adjacent_find() কী?

C++ এর <algorithm> লাইব্রেরিতে adjacent_find() একটি ফাংশন যা কোনো রেঞ্জের (যেমন: ভেক্টর, অ্যারে) মধ্যে দুটি পাশাপাশি উপাদান খুঁজে বের করে, যারা একই মান ধারণ করে বা কোনো নির্দিষ্ট শর্ত পূরণ করে। এটি প্রথম জোড়া পাশাপাশি উপাদানের ইটারেটর রিটার্ন করে। যদি এমন কোনো জোড়া না পাওয়া যায়, তবে রেঞ্জের শেষ ইটারেটর রিটার্ন করে।

সিনট্যাক্স

adjacent_find (ForwardIterator first, ForwardIterator last);
// অথবা
adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

first: রেঞ্জের শুরুর ইটারেটর।
last: রেঞ্জের শেষের ইটারেটর।
pred: একটি বাইনারি প্রেডিকেট (ঐচ্ছিক), যা দুটি উপাদানের মধ্যে তুলনা করে।

উদাহরণগুলো বাংলায় ব্যাখ্যা

উদাহরণ ১: ডিফল্ট adjacent_find()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 3, 4, 5};
    auto it = adjacent_find(v.begin(), v.end());
    if (it != v.end()) {
        cout << "পাশাপাশি একই উপাদান পাওয়া গেছে: " << *it << endl;
    } else {
        cout << "কোনো পাশাপাশি একই উপাদান নেই" << endl;
    }
    return 0;
}

আউটপুট: পাশাপাশি একই উপাদান পাওয়া গেছে: ২

ব্যাখ্যা: এখানে ভেক্টরে {1, 2, 2, 3, 4, 5} আছে। adjacent_find() দেখেছে যে ২ এবং ২ পাশাপাশি আছে। তাই প্রথম ২-এর ইটারেটর রিটার্ন করেছে।

উদাহরণ ২: কোনো পাশাপাশি একই উপাদান না থাকলে

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 3, 5, 7};
    auto it = adjacent_find(v.begin(), v.end());
    if (it != v.end()) {
        cout << "পাশাপাশি একই উপাদান পাওয়া গেছে: " << *it << endl;
    } else {
        cout << "কোনো পাশাপাশি একই উপাদান নেই" << endl;
    }
    return 0;
}

আউটপুট: কোনো পাশাপাশি একই উপাদান নেই

ব্যাখ্যা: এখানে {1, 3, 5, 7}-এ কোনো পাশাপাশি একই সংখ্যা নেই। তাই v.end() রিটার্ন করেছে।

উদাহরণ ৩: কাস্টম প্রেডিকেট ব্যবহার

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool sumEqualToTen(int a, int b) {
    return (a + b == 10);
}

int main() {
    vector<int> v = {3, 7, 4, 6, 5};
    auto it = adjacent_find(v.begin(), v.end(), sumEqualToTen);
    if (it != v.end()) {
        cout << "পাশাপাশি উপাদান যার সমষ্টি ১০: " << *it << " এবং " << *(it + 1) << endl;
    } else {
        cout << "এমন কোনো জোড়া নেই" << endl;
    }
    return 0;
}

আউটপুট: পাশাপাশি উপাদান যার সমষ্টি ১০: ৩ এবং ৭

ব্যাখ্যা: এখানে {3, 7, 4, 6, 5}-এ ৩ এবং ৭-এর সমষ্টি ১০। তাই প্রথম উপাদান ৩-এর ইটারেটর রিটার্ন করেছে।

Frequency Counter Algorithm: for String and Array Problem

on March 27, 2025 in Algorithm, array, C++, DSA, frequency counter, Python, string with No comments

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম: বাংলায় বিস্তারিত গাইড ও উদাহরণ

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম: বাংলায় বিস্তারিত গাইড

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম কী?

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম হলো একটি কার্যকর পদ্ধতি যা কোনো ডেটা সেটে প্রতিটি উপাদানের উপস্থিতির সংখ্যা গণনা করে। এটি সাধারণত অ্যারে, স্ট্রিং বা অন্যান্য ডেটা স্ট্রাকচারে প্রতিটি আইটেমের ফ্রিকোয়েন্সি নির্ণয়ে ব্যবহৃত হয়। এই অ্যালগরিদমটি দ্রুত এবং দক্ষতার সাথে কাজ করে।

কেন ফ্রিকোয়েন্সি কাউন্টার ব্যবহার করা হয়?

এই অ্যালগরিদমটি সময় জটিলতা কমাতে এবং ডেটা বিশ্লেষণে দ্রুত ফলাফল প্রদানে ব্যবহৃত হয়। উদাহরণস্বরূপ, কোনো তালিকায় কোনো সংখ্যা বা অক্ষর কতবার আছে তা জানতে এটি অত্যন্ত উপযোগী। এটি প্যাটার্ন ম্যাচিং, ডুপ্লিকেট চেকিং এবং ডেটা প্রস্তুতিতে গুরুত্বপূর্ণ ভূমিকা পালন করে।

কখন এটি ব্যবহার করবেন?

যখন আপনার কাছে একটি ডেটা সেট থাকবে এবং আপনি জানতে চাইবেন প্রতিটি উপাদান কতবার পুনরাবৃত্তি হয়েছে, তখন এই অ্যালগরিদমটি ব্যবহার করা হয়। উদাহরণস্বরূপ:

একটি স্ট্রিংয়ে প্রতিটি অক্ষরের সংখ্যা গণনা।
একটি অ্যারেতে ডুপ্লিকেট উপাদান খুঁজে বের করা।
দুটি ডেটা সেটের তুলনা করা।

বিস্তারিত ব্যাখ্যা: শুরু থেকে অ্যাডভান্সড লেভেল

এই অ্যালগরিদমটি ধাপে ধাপে বোঝার জন্য আমরা পাইথনে কোডের মাধ্যমে ৫টি উদাহরণ দেখব।

ধাপ ১: মৌলিক ধারণা

এই অ্যালগরিদমে আমরা একটি ডিকশনারি (হ্যাশ ম্যাপ) ব্যবহার করি। প্রতিটি উপাদানকে কী এবং এর ফ্রিকোয়েন্সিকে মান হিসেবে সংরক্ষণ করা হয়।

উদাহরণ ১: স্ট্রিংয়ে অক্ষর গণনা

                
def count_frequency(string):
    freq = {}
    for char in string:
        if char in freq:
            freq[char] += 1
        else:
            freq[char] = 1
    return freq

text = "বাংলা"
result = count_frequency(text)
print(result)

আউটপুট: {'ব': 1, 'া': 2, 'ং': 1, 'ল': 1}

ব্যাখ্যা: "বাংলা" স্ট্রিংয়ে "া" দুইবার এসেছে, বাকি অক্ষর একবার করে।

উদাহরণ ২: লিস্টে সংখ্যা গণনা

                
def count_numbers(arr):
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq

numbers = [1, 2, 3, 2, 1, 4]
result = count_numbers(numbers)
print(result)

আউটপুট: {1: 2, 2: 2, 3: 1, 4: 1}

ব্যাখ্যা: ১ এবং ২ দুইবার করে এসেছে, ৩ এবং ৪ একবার করে।

ধাপ ২: মাঝারি জটিলতার সমস্যা

উদাহরণ ৩: দুটি স্ট্রিং একই কিনা চেক করা

                
def same_frequency(str1, str2):
    if len(str1) != len(str2):
        return False
    freq1 = count_frequency(str1)
    freq2 = count_frequency(str2)
    return freq1 == freq2

print(same_frequency("abba", "baba"))  # True
print(same_frequency("abc", "def"))    # False

ব্যাখ্যা: "abba" এবং "baba" তে a=2, b=2 আছে, তাই True। "abc" এবং "def" ভিন্ন।

ধাপ ৩: অ্যাডভান্সড ব্যবহার

উদাহরণ ৪: ডুপ্লিকেট সংখ্যা খুঁজে বের করা

                
def find_duplicates(arr):
    freq = count_numbers(arr)
    duplicates = [key for key, value in freq.items() if value > 1]
    return duplicates

numbers = [1, 2, 3, 2, 4, 1, 5]
result = find_duplicates(numbers)
print(result)

আউটপুট: [1, 2]

ব্যাখ্যা: ১ এবং ২ দুইবার করে এসেছে, তাই ডুপ্লিকেট।

উদাহরণ ৫: সর্বাধিক ফ্রিকোয়েন্সি খুঁজে বের করা

                
def max_frequency(arr):
    freq = count_numbers(arr)
    max_item = max(freq, key=freq.get)
    return max_item, freq[max_item]

numbers = [1, 2, 2, 3, 2, 4]
item, count = max_frequency(numbers)
print(f"সর্বাধিক ফ্রিকোয়েন্সি: {item}, সংখ্যা: {count}")

আউটপুট: সর্বাধিক ফ্রিকোয়েন্সি: 2, সংখ্যা: 3

ব্যাখ্যা: ২ তিনবার এসেছে, যা সর্বাধিক।

উপসংহার

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম একটি শক্তিশালী এবং দক্ষ টুল যা সহজ থেকে জটিল সমস্যা সমাধানে ব্যবহৃত হয়। এটি O(n) সময় জটিলতায় কাজ করে এবং হ্যাশ ম্যাপের সাহায্যে দ্রুত ফলাফল দেয়। এই গাইড এবং উদাহরণগুলো আপনার কোডিং দক্ষতা বাড়াতে সাহায্য করবে।

Codeforces problem(800) :- Beautiful matrix

on March 24, 2025 in Algorithm, beautiful matrix solution, Codeforces with No comments

Beautiful Matrix সমস্যার সি++ সমাধান - বাংলা ব্যাখ্যা

এই পোস্টে আমরা "Beautiful Matrix" নামের একটি প্রোগ্রামিং সমস্যার সমাধান করবো সি++ ভাষায়। সমস্যাটির উদ্দেশ্য হলো একটি ৫×৫ ম্যাট্রিক্সে একটি "১" কে মাঝখানে (৩য় সারি, ৩য় কলাম) নিয়ে আসার জন্য সর্বনিম্ন কতগুলো মুভ লাগবে তা বের করা। প্রতিটি মুভে আমরা পাশাপাশি দুটি সারি বা কলাম অদলবদল করতে পারি। এখানে আমি আমার সমাধানের প্রতিটি লাইন বাংলায় বিস্তারিতভাবে ব্যাখ্যা করবো।

সমস্যার বিবরণ

আমাদের দেওয়া আছে একটি ৫×৫ ম্যাট্রিক্স যেখানে ২৪টি শূন্য (০) এবং একটি এক (১) আছে। আমাদের লক্ষ্য হলো এই "১" কে ম্যাট্রিক্সের মাঝখানে (৩য় সারি, ৩য় কলাম, বা ০-ভিত্তিক ইনডেক্সে ২,২) নিয়ে আসা। আমরা শুধু পাশের সারি বা কলাম অদলবদল করতে পারি।

সি++ কোড

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int n = 5;
    vector<vector<int>> matrix(n, vector<int>(n));
    int row, col;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> matrix[i][j];
            if(matrix[i][j] == 1) {
                row = i;
                col = j;
            }
        }
    }
    int moves = abs(row - 2) + abs(col - 2);
    cout << moves << endl;
    return 0;
}

লাইন বাই লাইন বাংলা ব্যাখ্যা

লাইন ১: `#include <bits/stdc++.h>`

এই লাইনটি সি++ এর স্ট্যান্ডার্ড লাইব্রেরির সব হেডার ফাইল ইনক্লুড করে। এটি আমাদের প্রয়োজনীয় সব ফাংশন যেমন vector, cin, cout, abs ইত্যাদি ব্যবহার করতে দেয়। এটি একটি শর্টকাট যা সাধারণত প্রতিযোগিতামূলক প্রোগ্রামিংয়ে ব্যবহৃত হয়।

লাইন ২: `using namespace std;`

এটি আমাদের std নেমস্পেসের সবকিছু সরাসরি ব্যবহার করার অনুমতি দেয়। যেমন, আমাদের std::cin এর পরিবর্তে শুধু cin লিখতে হবে।

লাইন ৪: `int main() {`

এটি প্রোগ্রামের মূল ফাংশন। প্রোগ্রাম শুরু হয় এখান থেকে এবং এটি একটি ইন্টিজার (পূর্ণসংখ্যা) রিটার্ন করে।

লাইন ৫: `const int n = 5;`

এখানে আমরা একটি ধ্রুবক (constant) ভেরিয়েবল n ডিফাইন করছি যার মান ৫। এটি ম্যাট্রিক্সের আকার নির্দেশ করে (৫×৫)। const মানে এটি পরিবর্তন করা যাবে না।

লাইন ৬: `vector<vector<int>> matrix(n, vector<int>(n));`

এটি একটি ৫×৫ ম্যাট্রিক্স তৈরি করে vector ব্যবহার করে। vector হলো একটি গতিশীল অ্যারে। এখানে:

vector<int>(n) মানে ৫টি ইন্টিজারের একটি ভেক্টর (ডিফল্ট মান ০)।
vector<vector<int>> matrix(n, ...) মানে ৫টি সারির একটি ভেক্টর, যেখানে প্রতিটি সারিতে ৫টি কলাম আছে।

ফলে আমরা একটি ৫×৫ ম্যাট্রিক্স পাই।

লাইন ৭: `int row, col;`

এখানে দুটি ভেরিয়েবল row এবং col ডিফাইন করা হয়েছে। এগুলো "১" এর বর্তমান সারি এবং কলামের ইনডেক্স সংরক্ষণ করবে।

লাইন ৮: `for(int i = 0; i < n; i++) {`

এটি একটি লুপ যা ০ থেকে ৪ পর্যন্ত চলে (মোট ৫ বার, কারণ n = 5)। এটি ম্যাট্রিক্সের প্রতিটি সারির জন্য কাজ করে। i হলো সারির ইনডেক্স।

লাইন ৯: `for(int j = 0; j < n; j++) {`

এটি একটি ভেতরের লুপ যা প্রতিটি সারির ৫টি কলামের জন্য চলে। j হলো কলামের ইনডেক্স।

লাইন ১০: `cin >> matrix[i][j];`

এটি ব্যবহারকারীর কাছ থেকে ইনপুট নেয় এবং matrix[i][j] পজিশনে সংরক্ষণ করে। আমরা ৫টি লাইনে ৫টি করে সংখ্যা ইনপুট দেবো।

লাইন ১১: `if(matrix[i][j] == 1) {`

এটি চেক করে যে বর্তমান পজিশনে (i, j) যদি "১" থাকে।

লাইন ১২: `row = i;`

যদি "১" পাওয়া যায়, তাহলে row ভেরিয়েবলে সেই সারির ইনডেক্স (i) সেট করা হয়।

লাইন ১৩: `col = j;`

একইভাবে, col ভেরিয়েবলে "১" এর কলামের ইনডেক্স (j) সেট করা হয়।

লাইন ১৪-১৫: `}` এবং `}`

এগুলো দুটি for লুপ বন্ধ করে। ইনপুট শেষে আমরা "১" এর পজিশন জানি।

লাইন ১৬: `int moves = abs(row - 2) + abs(col - 2);`

এটি সর্বনিম্ন মুভের সংখ্যা গণনা করে:

abs(row - 2): "১" এর বর্তমান সারি থেকে টার্গেট সারি (২) এর দূরত্ব। abs পরম মান দেয়।
abs(col - 2): "১" এর বর্তমান কলাম থেকে টার্গেট কলাম (২) এর দূরত্ব।
দুটির যোগফল হলো মোট মুভ।

এটি ম্যানহাটন দূরত্ব নামে পরিচিত।

লাইন ১৭: `cout << moves << endl;`

এটি moves এর মান প্রিন্ট করে এবং একটি নতুন লাইন যোগ করে।

লাইন ১৮: `return 0;`

এটি প্রোগ্রাম শেষ করে এবং ০ রিটার্ন করে, যা বোঝায় প্রোগ্রাম সফলভাবে চলেছে।

লাইন ১৯: `}`

এটি main ফাংশন বন্ধ করে।

উদাহরণ

ইনপুট:

ব্যাখ্যা: "১" আছে (১, ৪) পজিশনে। মুভ = |১-২| + |৪-২| = ১ + ২ = ৩।

আউটপুট: ৩

কেন এটি কাজ করে?

প্রতিটি মুভে "১" একটি পজিশন সরে। সারি এবং কলামের দূরত্ব আলাদাভাবে গণনা করে আমরা সর্বনিম্ন মুভ পাই। এটি সবচেয়ে দ্রুত এবং সহজ পদ্ধতি।

Problem link: https://codeforces.com/contest/263/problem/A

Sliding window algorithm in bangla : easy for all

on March 23, 2025 in Algorithm, C++, Python, Sliding window with No comments

স্লাইডিং উইন্ডো অ্যালগরিদম: বাংলায় বিস্তারিত গাইড (২০২৫)

স্লাইডিং উইন্ডো অ্যালগরিদম: বাংলায় বিস্তারিত গাইড

স্বাগতম! এই ব্লগে আমরা আলোচনা করবো স্লাইডিং উইন্ডো অ্যালগরিদম সম্পর্কে, যা প্রোগ্রামিং এবং অ্যালগরিদম সমাধানে একটি অত্যন্ত কার্যকরী টেকনিক। এটি কী, কীভাবে কাজ করে, কোথায় ব্যবহৃত হয়, এবং পাইথন ও সি++ এর একাধিক উদাহরণ সহ বিস্তারিতভাবে বাংলায় ব্যাখ্যা করা হবে।

স্লাইডিং উইন্ডো অ্যালগরিদম কী?

স্লাইডিং উইন্ডো হলো একটি অ্যালগরিদম টেকনিক যা একটি নির্দিষ্ট বা পরিবর্তনশীল আকারের "উইন্ডো" ব্যবহার করে ডেটা (যেমন অ্যারে বা স্ট্রিং) প্রক্রিয়া করে। এই উইন্ডোটি ডেটার উপর দিয়ে স্লাইড করে এবং প্রতিটি ধাপে নির্দিষ্ট কাজ সম্পন্ন করে। এটি সময় জটিলতা কমাতে অত্যন্ত কার্যকর।

এটি কীভাবে কাজ করে?

স্লাইডিং উইন্ডো টেকনিক প্রধানত দুই ধরনের হয়:

নির্দিষ্ট আকারের উইন্ডো (Fixed Size Window): উইন্ডোর আকার স্থির থাকে।
পরিবর্তনশীল আকারের উইন্ডো (Variable Size Window): উইন্ডোর আকার প্রয়োজন অনুযায়ী পরিবর্তিত হয়।

এটি ডেটার একটি অংশ প্রক্রিয়া করে এবং তারপর উইন্ডোটি সামনে সরিয়ে পরবর্তী অংশে যায়।

কোথায় ব্যবহৃত হয়?

স্লাইডিং উইন্ডো বিভিন্ন প্রোগ্রামিং সমস্যায় ব্যবহৃত হয়, যেমন:

সর্বাধিক বা সর্বনিম্ন উপ-অ্যারে খুঁজে বের করা।
নির্দিষ্ট যোগফলের উপ-অ্যারে খুঁজে পাওয়া।
স্ট্রিং-এ প্যাটার্ন ম্যাচিং।
ডেটা স্ট্রিম প্রক্রিয়াকরণ।

উদাহরণ ১: নির্দিষ্ট আকারের উইন্ডো (সর্বাধিক যোগফল)

ধরা যাক, আমাদের অ্যারে [1, -3, 2, 1, -1, 4] এবং আমরা ৩টি উপাদানের সর্বাধিক যোগফল চাই।

পাইথন কোড


arr = [1, -3, 2, 1, -1, 4]
k = 3  # উইন্ডোর আকার
max_sum = float('-inf')

for i in range(len(arr) - k + 1):
    window_sum = sum(arr[i:i + k])
    max_sum = max(max_sum, window_sum)
    print(f"উইন্ডো {i+1}: {arr[i:i + k]}, যোগফল: {window_sum}")

print(f"সর্বাধিক যোগফল: {max_sum}")

সি++ কোড


#include 
#include 
using namespace std;

int main() {
    vector arr = {1, -3, 2, 1, -1, 4};
    int k = 3;
    int max_sum = INT_MIN;

    for (int i = 0; i <= arr.size() - k; i++) {
        int window_sum = 0;
        for (int j = i; j < i + k; j++) {
            window_sum += arr[j];
        }
        max_sum = max(max_sum, window_sum);
        cout << "উইন্ডো " << i + 1 << ": ";
        for (int j = i; j < i + k; j++) cout << arr[j] << " ";
        cout << ", যোগফল: " << window_sum << endl;
    }
    cout << "সর্বাধিক যোগফল: " << max_sum << endl;
    return 0;
}

আউটপুট:

উইন্ডো 1: [1, -3, 2], যোগফল: 0
উইন্ডো 2: [-3, 2, 1], যোগফল: 0
উইন্ডো 3: [2, 1, -1], যোগফল: 2
উইন্ডো 4: [1, -1, 4], যোগফল: 4
সর্বাধিক যোগফল: 4

উদাহরণ ২: পরিবর্তনশীল আকারের উইন্ডো (নির্দিষ্ট যোগফল)

ধরা যাক, অ্যারে [1, -1, 2, 3, -2, 4] এবং আমরা যোগফল ৫ চাই।

পাইথন কোড


arr = [1, -1, 2, 3, -2, 4]
target = 5
curr_sum = 0
start = 0

for end in range(len(arr)):
    curr_sum += arr[end]
    while curr_sum > target and start <= end:
        curr_sum -= arr[start]
        start += 1
    if curr_sum == target:
        print(f"উপ-অ্যারে: {arr[start:end+1]}, যোগফল: {curr_sum}")

সি++ কোড


#include 
#include 
using namespace std;

int main() {
    vector arr = {1, -1, 2, 3, -2, 4};
    int target = 5;
    int curr_sum = 0, start = 0;

    for (int end = 0; end < arr.size(); end++) {
        curr_sum += arr[end];
        while (curr_sum > target && start <= end) {
            curr_sum -= arr[start];
            start++;
        }
        if (curr_sum == target) {
            cout << "উপ-অ্যারে: [";
            for (int i = start; i <= end; i++) {
                cout << arr[i] << (i < end ? ", " : "");
            }
            cout << "], যোগফল: " << curr_sum << endl;
        }
    }
    return 0;
}

আউটপুট:

উপ-অ্যারে: [2, 3], যোগফল: 5

উদাহরণ ৩: স্ট্রিং-এ স্লাইডিং উইন্ডো (দীর্ঘতম সাবস্ট্রিং)

ধরা যাক, স্ট্রিং "abcabcbb" এবং আমরা দীর্ঘতম সাবস্ট্রিং চাই যেখানে কোনো অক্ষর পুনরাবৃত্তি নেই।

পাইথন কোড


s = "abcabcbb"
char_map = {}
start = 0
max_length = 0
max_substring = ""

for end in range(len(s)):
    if s[end] in char_map and char_map[s[end]] >= start:
        start = char_map[s[end]] + 1
    else:
        if end - start + 1 > max_length:
            max_length = end - start + 1
            max_substring = s[start:end + 1]
    char_map[s[end]] = end

print(f"দীর্ঘতম সাবস্ট্রিং: {max_substring}, দৈর্ঘ্য: {max_length}")

সি++ কোড


#include 
#include 
#include 
using namespace std;

int main() {
    string s = "abcabcbb";
    unordered_map char_map;
    int start = 0, max_length = 0;
    string max_substring;

    for (int end = 0; end < s.length(); end++) {
        if (char_map.find(s[end]) != char_map.end() && char_map[s[end]] >= start) {
            start = char_map[s[end]] + 1;
        } else if (end - start + 1 > max_length) {
            max_length = end - start + 1;
            max_substring = s.substr(start, max_length);
        }
        char_map[s[end]] = end;
    }

    cout << "দীর্ঘতম সাবস্ট্রিং: " << max_substring << ", দৈর্ঘ্য: " << max_length << endl;
    return 0;
}

আউটপুট:

দীর্ঘতম সাবস্ট্রিং: abc, দৈর্ঘ্য: 3

সুবিধা ও অসুবিধা

সুবিধা:

সময় জটিলতা কমায় (O(n²) থেকে O(n))।
বাস্তবায়ন সহজ এবং বোঝা যায়।
অ্যারে ও স্ট্রিং উভয় ক্ষেত্রেই কার্যকর।

অসুবিধা:

সব সমস্যার জন্য উপযুক্ত নয়।
কিছু ক্ষেত্রে অতিরিক্ত মেমোরি লাগতে পারে।

উপসংহার

স্লাইডিং উইন্ডো অ্যালগরিদম প্রোগ্রামিং সমস্যা সমাধানের জন্য একটি শক্তিশালী এবং জনপ্রিয় টেকনিক। এই ব্লগে আমরা এটির বিস্তারিত ব্যাখ্যা, পাইথন ও সি++ এর উদাহরণ, এবং এর প্রয়োগ দেখেছি। এটি শিখে আপনি অনেক জটিল সমস্যা সহজে সমাধান করতে পারবেন।

স্লাইডিং উইন্ডো প্র্যাকটিস প্রবলেম

এখানে কিছু জনপ্রিয় প্রোগ্রামিং প্ল্যাটফর্ম থেকে স্লাইডিং উইন্ডো সম্পর্কিত সমস্যার লিঙ্ক দেওয়া হলো। এগুলো অনুশীলন করে আপনি আপনার দক্ষতা বাড়াতে পারেন।

>প্রিফিক্স সাম: সম্পূর্ণ ব্যাখ্যা বাংলায়!

on March 22, 2025 in Algorithm, C++, CodeChef, Codeforces, Competitive Programming, Data Structures, Optimization, Prefix Sum, problem solving, Python, Subarray Sum, Time Complexity with No comments

প্রিফিক্স সাম: সম্পূর্ণ ব্যাখ্যা বাংলায়

প্রিফিক্স সাম কি?

প্রিফিক্স সাম হল একটি অ্যালগোরিদম, যা একটি অ্যারের উপাদানগুলোর যোগফল সংরক্ষণের একটি পদ্ধতি। এটি ব্যবহার করে, আমরা যেকোনো সাবঅ্যারে তে যোগফল বের করতে পারি অতি দ্রুত সময়ে।

প্রিফিক্স সাম কেন ব্যবহার করা হয়?

ধরি, আপনার কাছে একটি অ্যারে রয়েছে: [1, 2, 3, 4, 5]. এখন আপনি চাইতেছেন, arr[l] থেকে arr[r] পর্যন্ত যোগফল বের করতে। আপনি চাইলে অন্যভাবে খুব সহজেই করতে পারবেন কিন্তু অনলাইন জাজে Time Limit Exceed(TLE) খেতে পারেন। আর এই সমস্যা খুব সহজেই আপনি প্রিফিক্স সামের সাহায্যে সমাধান করতে পারবেন।

প্রিফিক্স সাম ব্যবহার না করলে আপনাকে প্রতি বার লুপ চালাতে হয়। কিন্তু যদি প্রিফিক্স সাম ব্যবহার করেন তাহলে একবার হিসাব করে, পরবর্তী সময়গুলোতে আপনি মাত্র O(1) সময়ে কাজটি করতে পারবেন।

প্রিফিক্স সামের সুবিধা :

প্রিফিক্স সামের সুবিধা হল যে এটি একবার অ্যারের উপাদানগুলোর যোগফল হিসাব করে সংরক্ষণ করে। যার পরবর্তী সময়ে সাবঅ্যারের যোগফল বের করার জন্য আমাদের সময় O(1) থাকে।

যেমনঃ, প্রিফিক্স সাম তৈরি করতে সময় লাগবে O(n), এবং সাবঅ্যারের যোগফল বের করতে O(1) সময় লাগে।

প্রিফিক্স সাম গণনার উদাহরণ :

C++ উদাহরণ

#include
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    int prefix[n];
    prefix[0] = arr[0]; // প্রথম উপাদান কপি করছি
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i]; // প্রতিটি উপাদান যোগ করতে থাকছি
    }
    cout << "Prefix Sum Array: ";
    for (int i = 0; i < n; i++) {
        cout << prefix[i] << " "; // আউটপুট: 1 3 6 10 15
    }
    return 0;
}

Python উদাহরণ

def prefix_sum(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]  # প্রথম উপাদান কপি করছি
    for i in range(1, len(arr)):
        prefix[i] = prefix[i - 1] + arr[i]  # প্রতিটি উপাদান যোগ করতে থাকছি
    return prefix

arr = [1, 2, 3, 4, 5]
print("Prefix Sum Array:", prefix_sum(arr))  # আউটপুট: [1, 3, 6, 10, 15]

কিভাবে সাবঅ্যারের যোগফল বের করা যাবে?

যদি আপনি জানেন যে আপনার প্রিফিক্স সাম অ্যারে তৈরি হয়ে গেছে, তাহলে আপনার সাবঅ্যারের যোগফল O(1) সময়ে বের করা যাবে। এই কোডটি দেখুন:

C++ উদাহরণ

int rangeSum(int prefix[], int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];  // সাবঅ্যারের যোগফল বের করা
}

Python উদাহরণ

def range_sum(prefix, l, r):
    if l == 0:
        return prefix[r]
    return prefix[r] - prefix[l - 1]  # সাবঅ্যারের যোগফল বের করা

প্রিফিক্স সামের সুবিধা ও প্রয়োগ

প্রিফিক্স সামের সবচেয়ে বড় সুবিধা হলো, আপনি একবার যোগফল হিসাব করে সংরক্ষণ করে ফেললে, পরবর্তীতে সাবঅ্যারের যোগফল বের করতে মাত্র O(1) সময়ে কাজ করতে পারবেন। এতে আপনার প্রোগ্রাম আরও দ্রুত কাজ করবে।

প্রিফিক্স সাম ব্যবহার করে আপনি বিভিন্ন ধরনের সমস্যা যেমন, সাবঅ্যারের যোগফল, সাবঅ্যারের গড় বের করা, এবং অন্যান্য সংখ্যাসূচক সমস্যা সমাধান করতে পারবেন।

প্র্যাকটিস প্রবলেম

ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম

on March 03, 2022 in Algorithm, Algorithm Explanation, C++ Programming, Code Example, Computer Science, Insertion Sort, Python Programming, Sorting Algorithm, Sorting Techniques, Space Complexity, Time Complexity with 1 comment

ইনসার্শন সর্ট (Insertion Sort) অ্যালগরিদম: সহজে শেখার পদ্ধতি এবং কোড উদাহরণ

গত পর্বগুলোতে আমি সিলেকশন সর্ট(Selection sort) এবং বাবল সর্ট(Bubble sort) অ্যালগরিদম নিয়ে আলোচনা করেছিলাম এই পর্বে আরও একটি সহজ সর্টিং অ্যালগরিদম নিয়ে আলোচনা করবো নাম ইনসার্শন সর্ট(Insertion sort) ।

ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম :-

এই সর্টিং অ্যালগরিদমের মূল বিষয় হলো - একটি নির্দিষ্ট সংখ্যার জন্য এমন একটি জায়গা খুঁজে বের করা যেখানে সংখ্যাটিকে রাখলে তার আগের সংখ্যাটি তার থেকে ছোট বা সমান হবে এবং পরের সংখ্যাটি তার থেকে বড় হবে । তবে সংখ্যাটি যদি অ্যাঁরে বা লিস্টের সবচেয়ে ছোট বা বড় সংখ্যা হয় তাহলে তার জন্য সবার প্রথমে জায়গা করে দিতে হবে ।যেমন : - নিচের visualization টি লক্ষ্য করি :-

ধরি, আমাদের কাছে [10,30,40] এই অ্যাঁরেটি ছোট থেকে বড় ক্রমে সাজানো আছে । আমি এই অ্যাঁরেতে আরেকটি সংখ্যা যুক্ত করতে চাই সংখ্যাটি হলো 20 । এখন আমাকে 20 কে এমন এক জায়গায় বসাতে হবে যেখানে তার আগের সংখ্যা তার থেকে ছোট বা সমান হবে এবং তার পরের সংখ্যাটি তার থেকে বড় হবে ।

যদি অ্যাঁরেতে লক্ষ করি তাহলে দেখতে পারবো যে, সেই কাঙ্খিত জায়গাটি হচ্ছে 10 এর পরের অবস্থান কারণ, 20 থেকে 10 ছোট এবং 30 বড় । এখন যেহেতু 10 এর পরের অবস্থানে 30 আছে, তাহলে 30 এর জায়গায় 20 কে বসাতে হলে অ্যাঁরের শেষ থেকে অর্থাৎ 40 কে এক ঘর ডানে সরাতে হবে এখন 40 যেখানে ছিলো সেই ঘরটি কিন্তু ফাকা -

[10, 30, _, 40]

এরপর 30 কে এক ঘর ডানে সরাই - [10, _, 30, 40]

এখন ফাকা জায়গাটি কিন্তু 20 এর জন্য পারফেক্ট জায়গা অর্থাৎ, যে স্থানটি ফাকা তার আগের সংখ্যাটি 20 থেকে ছোট এবং পরের সংখ্যাটি 20 থেকে বড় । তাহলে ফাকা জায়গাটিতে 20 কে এসাইন করি -

[10, 20, 30, 40]

এতক্ষণ যে পদ্ধতিতে একটি সংখ্যা অ্যাঁরেতে সাজানো হলো এই পদ্ধতিকেই আমরা ইনসারশন সর্ট(Insertion sort) বলতে পারি ।

অ্যারে(Array) ও ইনসার্শন সর্ট(Insertion sort) -

তো চলুন এখন একটি এলোমেলো অ্যাঁরে বা লিস্টকে ইনসারশন সর্ট(Insertion sort) পদ্ধতিতে ছোট থেকে বড় ক্রমে বা Accending order এ সাজাই । ধরি, আমার কাছে একটি অ্যারে আছে -

[50, 20, 10, 30]

স্টেপ(০১) :- প্রথমে 50 এবং 20 এর মধ্যে ছোট সংখ্যার জন্য উপযুক্ত জায়গা খুঁজে বের করবো । এক্ষেত্রে, 20 কে 50 এর অবস্থানে বসাতে হবে তাই 50 কে এক ঘর ডানদিকে সরাই । এখন কিন্তু 50 এর জায়গা খালি তাই খালি জায়গায় 20 কে এসাইন করি -

[20, 50, 10, 30]

স্টেপ(০২) :- 50 এবং 10 এর মধ্যে 10 এর জন্য উপযুক্ত জায়গা খুঁজে বের করি । এক্ষেত্রে, অ্যারের প্রথমে 10 কে রাখতে হবে অর্থাৎ 20 এর অবস্থানে । তাই, প্রথমে 50 কে এক ঘর ডান দিকে সরাই - [20, _, 50, 30]

এখনও উক্ত ফাকা স্থানটি কিন্তু 10 এর উপযুক্ত জায়গা না তাই 20 কেও এক ঘর ডান দিকে সরাই - [_, 20, 50, 30] এখন ফাকা স্থানে অর্থাৎ 20 এর আগের ঘরে 10 এসাইন করি -

[10, 20, 50, 30]

স্টেপ(০৩) :- 50 এবং 30 এর মধ্যে 30 এর জন্য উপযুক্ত জায়গা খুঁজে বের করি এক্ষেত্রে, 20 এবং 50 এর মাঝে । তাই 50 কে এক ঘর ডানদিকে সরাই -

[10, 20, _, 50] এখন ফাকা জায়গাটিতে 30 কে এসাইন করি -

[10, 20, 30, 50]

ব্যাস, উপরোক্ত অ্যারে বা লিস্টটি ছোট থেকে বড় ক্রমে অর্থাৎ Accending order এ সাজানো হয়ে গেলো । এখন আপনি যদি বুঝতে না পারেন তাহলে খাতা-কলম নিয়ে বিষয়টি বোঝার চেষ্টা করতে পারেন । যদি প্রথম বা দ্বিতীয় বারে বিষয়টি বুঝে থাকেন তাহলে আপনি একটি বড় অ্যারে বা লিস্টকে খাতা-কলমে সর্ট করতে পারেন । তো চলুন এখন ইমপ্লিমেন্টেশন করা যাক -

In Python :

def insertionSort(arr):
    for i in range(1, len(arr)):
        # arr[i] কে currentValue তে এসাইন করি
        currentValue = arr[i]
        # currentValue এর জন্য উপযুক্ত স্থান খুঁজে বের করি
        j = i - 1
        # যদি j, 0 থেকে সমান বা বড় হয় এবং  arr[j] থেকে currentValue ছোট হয়
        while j >= 0 and arr[j] > currentValue:
            # arr[j] কে তার পরের ঘরে রেখে দিই
            arr[j+1] = arr[j]
            # j এর মান 1 করে কমাই
            j -= 1
        # এখন খালি জায়গায় currentValue কে বসাই
        arr[j+1] = currentValue
    return arr

In JavaScript :

function insertionSort(arr) {
  // একটি currentValue নামে ভেরিয়েবল নিই
  var currentValue;
  // i এর মান 1 থেকে len(arr) এর আগ পর্যন্ত 1 করে বাড়াই
  for (var i = 1; i < arr.length; i++) {
    // arr[i] কে currentValue তে এসাইন করি
    currentValue = arr[i];
    // currentValue এর জন্য উপযুক্ত স্থান খুঁজে বের করি (j = i - 1)
    // যদি j, 0 থেকে সমান বা বড় হয় এবং  arr[j] থেকে currentValue ছোট হয়
    for (var j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
      // arr[j] কে তার পরের ঘরে রেখে দিই
      arr[j + 1] = arr[j];
    }
    // এখন খালি জায়গায় currentValue কে বসাই
    arr[j + 1] = currentValue;
  }
  return arr;
}

আপনি চাইলে জাভাস্ক্রিপ্ট কোডে for লুপের পরিবর্তে while লুপ ব্যাবহার করতে পারেন ।

উপরোক্ত কোড বিশ্লেষণ :-

উপরের প্রোগ্রামে, প্রথমে i=1 থেকে অ্যারের লেন্থ পর্যন্ত লুপ চালিয়েছি । তারপর currentValue নামে একটি ভেরিয়েবলের মাঝে অ্যারের Present ভ্যালুকে রাখছি । এক্ষেত্রে কারেন্ট ভ্যালুটি যাতে হারিয়ে না যায় তা নিশ্চিত করছি কারণ পরবর্তীতে এই currentValue কেই তার যথাযথ স্থানে রাখতে হবে ।

তারপর ভেতরের লুপে j >= 0 এবং arr[j] > currentValue এইভাবে চেক করতেছি । এখানে, যদি j এর মান 0 থেকে ছোট হয় তাহলে আমি বুঝতে পারবো যে অ্যারে বা লিস্টের সব উপাদানই currentValue থেকে বড় । আবার, j এর মান যদি 0 থেকে বড় বা সমান হয় তাহলে দ্বিতীয় শর্তপরীক্ষা করা করবো অর্থাৎ arr[j] > currentValue ।

এখন যদি দ্বিতীয় শর্ত অর্থাৎ arr[j] > currentValue সত্য হয় তাহলে, arr[j] কে আমরা এক ঘর ডানে সরিয়ে দিব - arr[j + 1] = arr[j]

আবার, arr[j] > currentValue যদি মিথ্যা হয় তাহলে, লুপ থেকে বের হয়ে arr[j + 1] এ currentVal কে এসাইন করে দিব - arr[j + 1] = currentVal ইত্যাদি ।

যেকোনো অ্যালগরিদম বাঁ ডাটা-স্ট্রাকচারের মূল কনসেপ্ট যদি আপনি ভালোভাবে বুঝতে পারেন তাহলে যেকোনো প্রোগ্রামিং ল্যাঙ্গুয়েজ ব্যাবহার করেই ইমপ্লিমেন্ট করতে পারবেন । চলুন ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদমের টাইম ও স্পেস কমপ্লেক্সিটি বের করা যাক -

টাইম কমপ্লেক্সিটি(Time Complexity) :

উপরোক্ত কোড লক্ষ করলে আশা করি টাইম কমপ্লেক্সিটি(Time Complexity) বলে দিতে পারবেন । এই অ্যালগোরিদমেরও টাইম কমপ্লেক্সিটি(Time Complexity) O(n²) ।

স্পেস কমপ্লেক্সিটি(Space Complexity) :

উপরের প্রোগ্রামে একটু খেয়াল করলে দেখতে পারবো যে, প্রোগ্রামে একটি লিস্ট বা অ্যারে প্যারামিটার হিসেবে নেওয়া হয়েছে । এবং যা কাজ-কারবার করা হয়েছে তা এই অ্যারে বা লিস্টের মধ্যেই । এই অ্যারে বা লিস্টে কিন্তু কোনো নতুন উপাদান সংযোজন, বিয়োজন ইত্যাদি কিছুই করা হয় নাই । তাহলে বলতে পারি অ্যারে বা লিস্টটি Constant । এখন আপনার কাছে আমার প্রশ্ন এই প্রোগ্রামের স্পেস কমপ্লেক্সিটি(Space Complexity) কত ?

আশা করি পেরেছেন হ্যাঁ স্পেস কমপ্লেক্সিটি(Space Complexity) হচ্ছে - O(1) ।

ব্রাভো, যদি এতদূর পর্যন্ত আপনি ঠিকঠাক ভাবে পড়ে থাকেন তাহলে আমি ধরে নিতেই পারি ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম সম্পর্কে ভালো একটা দখল চলে আসছে ।

যদি সত্যি বুঝে থাকেন তাহলে একটি কাজ করতে পারেন, উপরোক্ত অ্যারেটিকে আমি কিন্তু Accending Order অর্থাৎ ছোট থেকে বড় ক্রমে সাজিয়েছি এখন আপনি ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম ব্যাবহার করে অ্যারেটিকে Decending Order অর্থাৎ বড় থেকে ছোট ক্রমে সাজানোর চেষ্টা করবেন । খুবই সহজ একটি কাজ আশা করি পারবেন শুভকামনা রইলো ।

চেক প্যালিনড্রোম (Palindrome) - using Stack

on February 02, 2022 in Algorithm, Algorithm Explanation, Arrays, Ascending Order Sorting, C++ Programming, Computer Science, Descending Order sorting, DSA, es6, Python, stack with No comments

Stack ডাটা-স্ট্রাকচার দিয়ে Palindrome প্রব্লেম সমাধান: জাভাস্ক্রিপ্ট এবং পাইথন ইমপ্লিমেন্টেশন

আমি বেশ কিছুদিন আগে Stack এবং Queue ডাটা-স্ট্রাকচার নিয়ে আলোচনা করেছিলাম সাথে জাভাস্ক্রিপ্ট এবং পাইথন দিয়ে ইমপ্লিমেন্টও করেছিলাম । তো আজকে আমি, একটি সুপরিচিত এবং সহজ প্রব্লেম নিয়ে আলোচনা করবো এবং Stack ডাটা-স্ট্রাকচার দিয়ে সমাধান করবো ।

আমরা জানি, Stack ডাটা-স্ট্রাকচার LIFO(Last In First Out) প্যারাডাইম মেনে চলে অর্থাৎ এখানে কোনো ভ্যালু শেষে এড করা হলে তা প্রথমে ডিলিট হয়ে যাবে । আপনি যদি Stack ও Queue ডাটা-স্ট্রাকচার সম্পর্কে না জেনে থাকেন তাহলে নিচের দেওয়া লিঙ্কগুলো থেকে পরে নিতে পারেন -

এখন, আসল কাজে ফিরে আসা যাক - আপনাকে একটি ফাংশন লিখতে হবে যা প্যারামিটার হিসেবে একটি স্ট্রিং নিবে । যদি স্ট্রিং টি Palindrome হয় তাহলে true নতুবা false রিটার্ন করবে ।

Palindrome String :-

যদি কোনো স্ট্রিং ডানে এবং বামে অর্থাৎ উভয় থেকে একই হয় তাহলে তাকে Palindrome String বলা যায় । যেমন :- mam, madam, racecar ইত্যাদি ।

এখন এই প্রব্লেমটি আমরা অনেক ভাবেই সমাধান করতে পারি আবার এক লাইনেও সমাধান করতে পারি । কিন্তু আমরা অন্যভাবে প্রব্লেমটি সমাধান না করে Stack দিয়ে কিভাবে সমাধান করতে হয় তা দেখবো এবং বোঝার চেষ্টা করবো ।

ধরি, আমাদের কাছে একটি স্ট্রিং আছে "MaM" । আমরা চাইলে সরাসরি Stack ডাটা-স্ট্রাকচার ইমপ্লিমেন্ট করে তা দিয়ে সমাধান করতে পারি । কিন্তু, Stack ডাটা-স্ট্রাকচার সরাসরি ইমপ্লিমেন্ট না করেও জাভাস্ক্রিপ্টের অ্যারে অথবা পাইথনের লিস্ট দিয়ে খুব সহজেই Stack এর কাজ করে ফেলতে পারি তো চলুন শুরু করা যাক -

স্টেপ(০১) :- প্রথমে, "MaM" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "M" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "M" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["M"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "a" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["M", "a"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "M" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["M", "a", "M"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে -

word = ""

এখন contains অ্যারে থেকে শেষের ভ্যালুকে রিমুভ অর্থাৎ pop() করে word স্ট্রিং এর মধ্যে রাখলাম । এখন contains অ্যারে হবে ২ উপাদান বিশিষ্ট এবং word স্ট্রিং টি হবে ১ উপাদান বিশিষ্ট -

word = "M"

contains = ["M", "a"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "Ma"

contains = ["M"]

এখন, contains অ্যারে তে একটি মাত্র উপাদানই আছে সেইটাকেও রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "MaM"

contains = []

এই word হলো আমাদের নতুন স্ট্রিং, এখন এই word এর সাথে function এর প্যারামিটার তুলনা করবো যদি দুইটা সমান হয় তাহলে true নতুবা false রিটার্ন করবে ।

যেহেতু, আমাদের প্যারামিটার এবং word এর মান একই সেহেতু "MaM" একটি Palindrome স্ট্রিং ।

আরেকটি উদাহরণ :-

ধরি আমাদের কাছে একটি str নামে স্ট্রিং আছে,

str = "abc" ।

স্টেপ(০১) :- প্রথমে, "abc" স্ট্রিং এর প্রত্যেকতা উপাদানকে একটি অ্যারে বা লিস্টে রাখতে হবে । সেক্ষেত্রে, আমাদের একটি ফাকা লিস্ট বা অ্যারে নিতে হবে -

contains = []

এরপর, স্ট্রিং এর প্রথম উপাদান "a" কে contains নামের অ্যারে বা লিস্টে এ পুশ করে দেই । এক্ষেত্রে, কিন্তু "a" উপাদানকে contains নামের অ্যারের শেষে রাখলাম । এখন অ্যারেটি যদি দেখি -

contains = ["a"]

স্টেপ(০২) :- এখন স্ট্রিং এর দ্বিতীয় উপাদান অর্থাৎ "b" কে contains নামের অ্যারে বা লিস্টে পুশ করে দেই । আবারও বলি পুশ করা মানে কিন্তু উপাদানকে অ্যারের শেষে যুক্ত করা এখন অ্যারেটি যদি আবার দেখি -

contains = ["a", "b"]

স্টেপ(০৩) :- স্ট্রিং এর শেষ উপাদান অর্থাৎ "c" কে contains নামের অ্যারে বা লিস্টে পুশ করে দিলাম -

contains = ["a", "b", "c"]

এখন লিস্ট বা অ্যারে থেকে প্রত্যেকটা উপাদান pop() করবো । pop() মানে হলো, যে উপাদানটি আমরা সবার শেষে এড করেছি সেই উপাদান এখন সবার প্রথমে রিমুভ করে অন্য স্ট্রিং এ রাখবো । তারপর ফাংশনে প্যারামিটার হিসেবে পাওয়া স্ট্রিং এর সাথে তুলনা করে দেখবো যে স্ট্রিং টি Palindrome কি না ।

একটা ফাকা স্ট্রিং নিলাম word নামে -

word = ""

word = "c"

contains = ["a", "b"]

আবার, contains অ্যারে থেকে শেষের ভ্যালু রিমুভ অর্থাৎ pop() করে word এর মধ্যে রাখলাম -

word = "cb"

contains = ["a"]

word = "cba"

contains = []

যেহেতু, আমাদের প্যারামিটার ছিলো "abc" এবং word এর মান "cba" সেহেতু "abc" একটি Palindrome স্ট্রিং নয়।

তো চলুন এখন কোড লিখা যাক -

জাভাস্ক্রিপ্টে ইমপ্লিমেন্টেশন -

const isPalindrome = (str) => {
  let contains = [];
  for (let i = 0; i < str.length; i++) {
    contains.push(str[i]);
  }

  let word = "";
  while (contains.length > 0) {
    word += contains.pop();
  }
  return word === str;
};

Output :

isPalindrome("MaM");  // true
isPalindrome("abc"); // false

পাইথনে ইমপ্লিমেন্টেশন :-

def isPalindrome(str):
    contains = []
    for item in str:
        contains.append(item)

    word = ""
    while len(contains) > 0:
        word += contains.pop()

    return word == str

Output :

isPalindrome("MaM"); # True
isPalindrome("abc"); # False

কোড বিশ্লেষণ :-

উপরোক্ত কোডে, প্রথমে contains নামে একটি অ্যারে বা লিস্ট নিয়েছি । তারপর, স্ট্রিং এ লুপ থ্রু করেছি এবং প্রত্যেকতা উপাদানকে contains নামের অ্যারে বা লিস্টে পুশ করে দিয়েছি ।

word নামে একটি ফাকা স্ট্রিং নিয়েছি এবং contains অ্যারেতে একটি লুপ থ্রু করেছি । লুপটি ততক্ষণ চলবে যতক্ষণ পর্যন্ত contains এর সাইজ 0 থেকে বড় থাকবে । এবং প্রত্যেক ইটারেশনে word এর সাথে contains এর শেষ উপাদানটি রিমুভ হয়ে যোগ হতে থাকবে । এক পর্যায়ে আমাদের লুপটি শেষ হবে । তখন যদি word এবং str সমান হয় তাহলে funciton টি আমাদেরকে true রিটার্ন করবে নতুবা false রিটার্ন করবে ।

কোডের টাইম ও স্পেস উভয় কমপ্লেক্সিটি হবে ওর্ডার অব এন অর্থাৎ O(n) ।

Saturday, 29 March 2025

adjacent_find() কী?

সিনট্যাক্স

উদাহরণগুলো বাংলায় ব্যাখ্যা

উদাহরণ ১: ডিফল্ট adjacent_find()

উদাহরণ ২: কোনো পাশাপাশি একই উপাদান না থাকলে

উদাহরণ ৩: কাস্টম প্রেডিকেট ব্যবহার

Thursday, 27 March 2025

ফ্রিকোয়েন্সি কাউন্টার অ্যালগরিদম কী?

কেন ফ্রিকোয়েন্সি কাউন্টার ব্যবহার করা হয়?

কখন এটি ব্যবহার করবেন?

বিস্তারিত ব্যাখ্যা: শুরু থেকে অ্যাডভান্সড লেভেল

ধাপ ১: মৌলিক ধারণা

উদাহরণ ১: স্ট্রিংয়ে অক্ষর গণনা

উদাহরণ ২: লিস্টে সংখ্যা গণনা

ধাপ ২: মাঝারি জটিলতার সমস্যা

উদাহরণ ৩: দুটি স্ট্রিং একই কিনা চেক করা

ধাপ ৩: অ্যাডভান্সড ব্যবহার

উদাহরণ ৪: ডুপ্লিকেট সংখ্যা খুঁজে বের করা

উদাহরণ ৫: সর্বাধিক ফ্রিকোয়েন্সি খুঁজে বের করা

উপসংহার

Monday, 24 March 2025

Beautiful Matrix সমস্যার সি++ সমাধান - বাংলা ব্যাখ্যা

সমস্যার বিবরণ

সি++ কোড

লাইন বাই লাইন বাংলা ব্যাখ্যা

লাইন ১: #include <bits/stdc++.h>

লাইন ২: using namespace std;

লাইন ৪: int main() {

লাইন ৫: const int n = 5;

লাইন ৬: vector<vector<int>> matrix(n, vector<int>(n));

লাইন ৭: int row, col;

লাইন ৮: for(int i = 0; i < n; i++) {

লাইন ৯: for(int j = 0; j < n; j++) {

লাইন ১০: cin >> matrix[i][j];

লাইন ১১: if(matrix[i][j] == 1) {

লাইন ১২: row = i;

লাইন ১৩: col = j;

লাইন ১৪-১৫: } এবং }

লাইন ১৬: int moves = abs(row - 2) + abs(col - 2);

লাইন ১৭: cout << moves << endl;

লাইন ১৮: return 0;

লাইন ১৯: }

উদাহরণ

কেন এটি কাজ করে?

Problem link: https://codeforces.com/contest/263/problem/A

Sunday, 23 March 2025

স্লাইডিং উইন্ডো অ্যালগরিদম: বাংলায় বিস্তারিত গাইড

স্লাইডিং উইন্ডো অ্যালগরিদম কী?

এটি কীভাবে কাজ করে?

কোথায় ব্যবহৃত হয়?

উদাহরণ ১: নির্দিষ্ট আকারের উইন্ডো (সর্বাধিক যোগফল)

পাইথন কোড

সি++ কোড

উদাহরণ ২: পরিবর্তনশীল আকারের উইন্ডো (নির্দিষ্ট যোগফল)

পাইথন কোড

সি++ কোড

উদাহরণ ৩: স্ট্রিং-এ স্লাইডিং উইন্ডো (দীর্ঘতম সাবস্ট্রিং)

পাইথন কোড

সি++ কোড

সুবিধা ও অসুবিধা

উপসংহার

স্লাইডিং উইন্ডো প্র্যাকটিস প্রবলেম

Saturday, 22 March 2025

প্রিফিক্স সাম কি?

প্রিফিক্স সাম কেন ব্যবহার করা হয়?

প্রিফিক্স সামের সুবিধা :

প্রিফিক্স সাম গণনার উদাহরণ :

C++ উদাহরণ

Python উদাহরণ

কিভাবে সাবঅ্যারের যোগফল বের করা যাবে?

C++ উদাহরণ

Python উদাহরণ

প্রিফিক্স সামের সুবিধা ও প্রয়োগ

প্র্যাকটিস প্রবলেম

Thursday, 3 March 2022

ইনসার্শন সর্ট(Insertion sort) অ্যালগরিদম :-

অ্যারে(Array) ও ইনসার্শন সর্ট(Insertion sort) -

In Python :

In JavaScript :

লাইন ১: `#include <bits/stdc++.h>`

লাইন ২: `using namespace std;`

লাইন ৪: `int main() {`

লাইন ৫: `const int n = 5;`

লাইন ৬: `vector<vector<int>> matrix(n, vector<int>(n));`

লাইন ৭: `int row, col;`

লাইন ৮: `for(int i = 0; i < n; i++) {`

লাইন ৯: `for(int j = 0; j < n; j++) {`

লাইন ১০: `cin >> matrix[i][j];`

লাইন ১১: `if(matrix[i][j] == 1) {`

লাইন ১২: `row = i;`

লাইন ১৩: `col = j;`

লাইন ১৪-১৫: `}` এবং `}`

লাইন ১৬: `int moves = abs(row - 2) + abs(col - 2);`

লাইন ১৭: `cout << moves << endl;`

লাইন ১৮: `return 0;`

লাইন ১৯: `}`